Диссертация (1137145), страница 18
Текст из файла (страница 18)
В выдвинутопредположение, о том что вычислительная сложность алгоритмапоиска k-ближайших k-NNSearch оценивается как O(log ()! )5.Произведеноисследованиепредложенныхалгоритмов,включающее большой сравнительный анализ эффективностиалгоритмов с существующими алгоритмами поиска ближайшегососеда,продемонстрировавшеезначительноепревосходствопредложенных алгоритмов.6.Предложена математическая модель оптимальной структурыграфа для поиска ближайшего соседа.1257.Найдены решения точные и эвристические решения предложенноймодели оптимальной структуры графа для некоторых частныйслучаев целочисленной решетки.Таким образом, учитывая полилогарифмическую сложность всехпредложенных алгоритмов, и факт использования алгоритмами тольколокальной информации о структуре сети, это даёт основания полагать, чторезультаты данной диссертации, открывают возможность для созданияраспределённых систем со сложной поисковой функциональностьюспособных к расширению до масштабов всемирной паутины.126Публикации по теме диссертацииСтатьи в рецензируемых изданиях, рекомендованных ВАК:1.
Alexander Ponomarenko, Yury Malkov, Andrey Logvinov, VladimirKrylov.. AN OVERLAY NETWORK FOR DISTRIBUTED EXACT ANDRANGE SEARCH IN ONE-DIMENSIONAL SPACE //Бизнесинформатика. – 2016. – №. 1 (35). – С. 26-36.2. Пономаренко А. А., Мальков Ю. А., Логвинов А. А., Крылов В.В. Структура со свойствами тесного мира для решения задачипоиска ближайшего соседа в метрическом пространстве // ВестникНижегородского университета им. Н.И. Лобачевского. 2012. № 5.С. 409-415.3. Мальков Ю.
А., Ponomarenko A. Growing Homophilic Networks AreNatural Navigable Small Worlds // Plos One. 2016. Vol. 11. No. 6 doi4. Ponomarenko A. Query-Based Improvement Procedure and Self-AdaptiveGraph Construction Algorithm for Approximate Nearest Neighbor Search//International Conference on Similarity Search and Applications.
–Springer International Publishing, 2015. – С. 314-319.5. Malkov Yury., Ponomarenko Alexander, Krylov Vladimir., LogvinovAndrey. Approximate nearest neighbor algorithm based on navigablesmall world graphs // Information Systems . 2014. Vol. 45. No. DOI10.1016/j.is.2013.10.006. P. 61-68.6.
Yury M., Ponomarenko A., Vladimir K., Logvinov A. ScalableDistributed Algorithm for Approximate Nearest Neighbor Search Problemin High Dimensional General Metric Spaces // Lecture Notes in ComputerScience. 2012. No. 7404. P. 132-147.Статьи в индексируемых РИНЦ:7. Пономаренко А. А., Аврелин Н. С., Найдан Б. С., Бойцов Л. М.СРАВНИТЕЛЬНЫЙАНАЛИЗСТРУКТУРДАННЫХДЛЯПРИБЛИЖЕННОГО ПОИСКА БЛИЖАЙШЕГО СОСЕДА //Алгоритмы, методы и системы обработки данных. 2015. Т. 4. № 33.С.91-106.Cтатьи в сборниках трудов конференций:8.
Alexander Ponomarenko, Nikita Avrelin, Bilegsaikhan Naidan, LeonidBoytsov. Comparative Analysis of Data Structures for ApproximateNearest Neighbor Search // Lecture Notes in Computer Science. 2014.ISBN: 978-1-61208-358-2 P. 125-131279. Пономаренко А. А. Организация быстрого поиска без индекса // Вкн.: Труды 38-й конференции "Информационные технологии исистемы - 2014".
Н. Новгород . 2014.10. Ponomarenko A., Malkov Y., Logvinov A., Krylov V. ApproximateNearest Neighbor Search Small World Approach //InternationalConference on Information and Communication Technologies &Applications. – 2011.11. Krylov V., Logvinov A., Ponomarenko A., Ponomarev D. Activedatabase architecture for XML documents , in: Proceedings of the ISCA23rd International Conference on Computer Applications in Industry andEngineering (CAINE), 2008.12. Ponomarenko A., Malkov Y., Krylov V., Logvinov A.
Metrized SmallWorld Approach for Nearest Neighbor Search , in: Proceedings of the 4thSpring/Summer Young Researchers’ Colloquium on SoftwareEngineering, SYRCoSE// Труды 4-ого Весеннего/летнего коллоквиумамолодых исследователей в области программной инженерии(SYRCoSE 2010), 1-2 июня 2010 г. – Нижний Новгород, Россия / Ed.by A. Kamkin, A. Petrenko, A. Terekhov.
Nizhny Novgorod, 2010.P. 151-156.13. Ponomarenko A., Krylov V., Logvinov A., Ponomarev D. Metrized smallworld properties data structure //Proceedings of the 17th InternationalConference on Software Engineering and Data Engineering (SEDE), LosAngeles, California, June 30 to July 2, 2008, P. 203-208.Препринты:14. Ponomarenko A., Utkina I., Batsyn M. A Model of Optimal NetworkStructure for Decentralized Nearest Neighbor Search //arXiv preprintarXiv:1712.08437.–2017.Свидетельства:1.
«Skoal - Cистема поиска химических соединений по структурномусходству» – свидетельство о государственной регистрациипрограммы для ЭВМ №2012619905. Правообладатель - ООО«МераЛабс».2. «Cloud MSW - Система облачного хранения данных с возможностьюпоиска в метрическом пространстве» – свидетельство огосударственной регистрации программы для ЭВМ №2012612167.Право обладатель - ООО «МераЛабс».128Список литературы1. МаксимовЮ.А.Алгоритмылинейногоидискретногопрограммирования. — М.: МИФИ, 1980.2. Adar E., Huberman B. A. Free riding on Gnutella //First monday.
– 2000.– Т. 5. – №. 10.3. Albert R., Barabási A. L. Statistical mechanics of complex networks//Reviews of modern physics. – 2002. – Т. 74. – №. 1. – С. 47.4. Albitz, P., & Liu, C. (1998). DNS and BIND. O'Reilly & Associates.5. Amato G., Savino P. Approximate similarity search in metric spaces usinginverted files //Proceedings of the 3rd international conference onScalable information systems. – ICST (Institute for Computer Sciences,Social-Informatics and Telecommunications Engineering), 2008.
– С. 28.6. CoDeeN.(2003).(PrincetonUniversity)FromCoDeeN:http://codeen.cs.princeton.edu/7. Beaumont O., Kermarrec A.-M., Rivière É. Peer to peer multidimensionaloverlays: approximating complex structures // Proceedings of the 11thInternational Conference on Principles of Distributed Systems. Berlin,Heidelberg, 2007.
P. 315–328.8. Boguna M., Krioukov D., Claffy K. C. Navigability of complex networks//Nature Physics. – 2009. – Т. 5. – №. 1. – С. 74-80.9. Bolettieri P. et al. CoPhIR: a test collection for content-based imageretrieval //arXiv preprint arXiv:0905.4627. – 2009.10. Bollobás B., Riordan O. M. Mathematical results on scale-free randomgraphs //Handbook of graphs and networks: from the genome to theinternet. – 2003. – С.
1-34.11. Boytsov L., Naidan B., Engineering Efficient and Effective Non-metricSpace Library //Similarity Search and Applications. – Springer BerlinHeidelberg, 2013. – С. 280-29312912. Boytsov L., Naidan B. Learning to prune in metric and non-metricspaces //Advances in Neural Information Processing Systems. – 2013.
–С. 1574-158213. Blei D. M., Ng A. Y., Jordan M. I. Latent dirichlet allocation //theJournal of machine Learning research. – 2003. – Т. 3. – С. 993-1022.14. Cattell R.. Scalable SQL and NoSQL data stores: ACM SIGMODRecord, 2011, т. 39, вып. 4, с. 12-27, ACM New York, NY, USA15. Cayton L. Fast nearest neighbor retrieval for bregman divergences//Proceedings of the 25th international conference on Machinelearning. – ACM, 2008.
– С. 112-119.16. Chaintreau A., Fraigniaud P., Lebhar E. Networks become navigable asnodes move and forget //Automata, Languages and Programming. – 2008.– С. 133-144.17. Chávez E. et al. Searching in metric spaces //ACM computingsurveys (CSUR). – 2001. – Т. 33. – №. 3. – С. 273-321.18. Chávez E., Navarro G. A compact space decomposition for effectivemetric indexing //Pattern Recognition Letters. – 2005.
– Т. 26. – №. 9. –С. 1363-1376.19. Chávez E., Navarro G. Probabilistic proximity search: Fighting the curseof dimensionality in metric spaces //Information Processing Letters. –2003. – Т. 85. –№. 1. – С. 39-46.20. Clauset A., Moore C. How do networks become navigable? //arXivpreprint cond-mat/0309415. – 2003.21.
Cox, R., Muthitacharoen, A., & Morris, R. (2002). Serving DNS Using aPeer-to-Peer Lookup Service. IPTPS.22. Dong W. et al. Modeling lsh for performance tuning //Proceedingsofthe 17th ACM conference on Information and knowledgemanagement. – ACM, 2008. –С. 669-678.13023. Douligeris C., Mitrokotsa A. DDoS attacks and defense mechanisms:classification and state-of-the-art //Computer Networks. – 2004.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
