Индексирование данных в пространстве большой размерности
Ключевые слова:
индексирование, поиск ближайшего соседа, данные большой размерности, анализ данных, редукция размерностиАннотация
Индексирование данных является неотделимой частью задачи поиска. В то время как для данных в пространствах размерностей не более 5 существует хорошо изученный набор эффективных алгоритмов индексации и поиска, для пространств большой размерностей эти алгоритмы оказываются неэффективны или неприменимы. В этом обзоре мы приводим существующие обоснования проблем связанных с индексированием в пространствах большой размерности для задачи поиска ближайшего соседа. Рассматриваются возможные методы решения обозначенных проблем, применимые в областях анализа данных, таких как кластеризация и извлечение скрытых структур. Ставится вопрос о применимости различных методов размерностной редукции к задачи индексирования и поиска ближайшего соседа.Литература
1. Donoho D. L. High-dimensional data analysis: the curses and blessings of dimensionality // American Mathematical Society Conf. Math Challenges of the 21st Century 2000.
2. Manning C.D., Raghavan P., Sch¨utze H. Introduction to Information Retrieval // American Mathematical Society Conf. Math Challenges of the 21st Century 2000.
3. Augenlicht L. H., Kobrin D. Cloning and Screening of Sequences Expressed in a Mouse Colon Tumor // Cancer Research. 1982. vol.42. pp. 1088-1093.
4. Dash M., Liu H. Feature Selection for Classification // Intelligent Data Analysis. 1997. vol.1. pp. 131-156.
5. Jain A.K., Duin R.P.W., Jianchang M. Statistical pattern recognition: a review // Pattern Analysis and Machine Intelligence, IEEE Transactions on. 2000. vol.22. pp. 4-37.
6. Koller D., Sahami M. Toward optimal feature selection // In 13th International Conference on Machine Learning. 1995. pp. 284–292.
7. Glazko G., Coleman M., Mushegian A. Similarity searches in genome-wide numerical data sets // Biology Direct. 2006. vol.1.
8. Yan T., Ganesan D., Manmatha R. Distributed Image Search in Sensor Networks // Proceeding SenSys ’08 Proceedings of the 6th ACM conference on Embedded network sensor systems. 2008.
9. Deshpande A., Guestrin C., Madden S.R., Hellerstein J.M., Hongn W. Model-driven data acquisition in sensor networks // Proceeding VLDB ’04 Proceedings of the Thirtieth international conference on Very large data bases. 2004. vol.30. pp. 588-599.
10. Russell S.J., Norvig P., Canny J.F., Malik J.M. Edwards D.D. Artificial intelligence: a modern approach // Prentice hall Englewood Cliffs. 1995.
11. Bellman R. E. Dynamic programming // Princeton University Press. 1957.
12. Beyer K., Goldstein J., Ramakrishnan R., Shaft U. When Is Nearest Neighbor Meaningful // ICDT ’99 Proceedings of the 7th International Conference on Database Theory. 1999. pp. 217-235.
13. Hinneburg A., Aggarwal C., Keim D.A. What Is the Nearest Neighbor in High Dimensional Spaces // VLDB ’00 Proceedings of the 26th International Conference on Very Large Data Bases. 2000. pp. 506-515.
14. Kriegel H.-P., Kr¨oger P., Zimek A. Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering // ACM Transactions on Knowledge Discovery from Data. 2009. vol.3 no.3. pp. 506-515.
15. Parsons L., Haque E., Liu H. Subspace clustering for high dimensional data: a review // ACM SIGKDD Explorations Newsletter - Special issue on learning from imbalanced dataset. 2004. vol.6.
16. B¨ohm C., Berchtold S., Keim D.A. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases // ACM Computing Surveys (CSUR). 2001. no.33. vol.3.
17. Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching // Proceedings of 1984 ACM SIGMOD International Conference on Management of Data. 1984. pp. 47-57.
18. Weber R., Schek H.-J., Blott S. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces // VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases. 1998. pp. 194-205.
19. Berchtold S., Keim D. A., Kriegel H.-P. The X-tree: An Index Structure for High-Dimensional Data // VLDB ’96 Proceedings of the 22th International Conference on Very Large Data Bases. 1996. pp. 28-39.
20. Pearson K. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions // Philosophical Magazine Bases. 1901. vol.2. pp. 559-572.
21. Gunnemann S., Kremer H., Lenhard D., Seidl T. Subspace Clustering for Indexing High Dimensional Data:A Main Memory Index based on Local Reductions and Individual Multi-Representations // Proc. International Conference on Extending Database Technology. 2011. pp. 237-248.
22. M¨uller E., Assent I., G¨unnemann S., Krieger R., Seidl T. Relevant Subspace Clustering: Mining the Most Interesting Non-Redundant Concepts in High Dimensional Database // Proc. IEEE International Conference on Data Minings. 2009. pp. 377-386.
23. Assent I., Krieger R., Miller E., Seidl T. INSCY:Indexing subspace clusters with in-process-removal of redundancy // Data Mining, 2008. ICDM ’08. Eighth IEEE International Conference. 2008. pp. 719-724.
24. Assent I., Krieger R., Miller E., Seidl T. EDSC: efficient density-based subspace clustering // Proceedings of the 17th ACM conference on Information and knowledge management. 2008. pp. 1093–1102.
25. Houle M. E., Kriegel H.-P., Kr¨oger P., Schubert E., Zimek A. Can Shared- Neighbor Distances Defeat the Curse of Dimensionality? // Scientific and Statistical Database Management. 2010. pp. 482-500.
26. Strehl A., Ghosh J. Cluster ensembles — a knowledge reuse framework for combining multiple partitions // The Journal of Machine Learning Research. 2003. pp. 583-617.
27. Aggarwal C.C., Wolf J.L., Phillip S., Yu C.P., Jong S.P. Fast algorithms for projected clustering // Proceedings of the 1999 ACM SIGMOD international conference on Management of data. 1999. pp. 61–72.
28. Nagesh H., Goil S. Adaptive Grids for Clustering Massive Data Sets // SIAM International Conference on Data Mining - SDM. 2002.
29. Fan J., Fan Y., Wu Y. High-dimensional classification // World Scientific, New Jersey. 2011. pp. 3-37.
30. Silverman B. Density Estimation for Statistics and Data Analysis // Monographs on Statistics and Applied Probability, London: Chapman and Hall. 1986.
31. Huber P.J. Projection Pursuit // The Annalas of Statistics. 1985. vol.2. no.13. pp. 435—475.
32. Friedman J.H. Exploratory projection pursuit // Journal of American Statistical Association. 1987. no.82. pp. 249—266.
33. Dobkin D., Lipton R.J. Multidimensional Searching Problems // SIAM Journal on Computing. 1974. no.5. pp. 181–186.
34. Meiser S. Point location in arrangemenm of hyperplanes // Information and Computation. 1993. no.106. pp. 286–303.
35. Andoni A., Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions // Communications of the ACM - 50th anniversary issue. 2008. vol.51. pp. 117-122.
36. Indyk P., Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998. pp. 604-613.
37. Datar M., Immorlica N., Indyk P., Mirrokni V.S. Locality-sensitive hashing scheme based on p-stable distributions // Proceedings of the twentieth annual symposium on Computational geometry. 2004. pp. 253-262.
38. Deegalla S., Bostrom H. Reducing High-Dimensional Data by Principal Component Analysis vs. Random Projection for Nearest Neighbor Classification // Proceedings of the 5th International Conference on Machine Learning and Applications. 2006. pp. 245-250.
39. Ian J. Principal component analysis // Wiley Online Library. 2005.
40. Gorban A. N. Principal manifolds for data visualization and dimension reduction // Springer. 2007. vol.58.
41. Tenenbaum J.B., De Silva V., Langford J.C. A global geometric framework for nonlinear dimensionality reduction // Science. 2000. vol.290. no.5500. pp. 2319–2323.
42. Kruskal J.B. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis // Psychometrika. 1964. vol.29. no.1. pp. 1-27.
43. Cox T.F., Cox M.A.A. Multidimensional scaling // CRC Press. 2010.
44. Heisterkamp D.R., Peng J. Kernel VA-files for relevance feedback retrieval // Proceedings of the 1st ACM international workshop on Multimedia databases. 2003. pp. 48-54.
45. Heisterkamp D.R., Peng J. Sparse subspace clustering // IEEE Conference on Computer Vision and Pattern Recognition CVPR 2009. 2009. pp. 2790-2797.
46. Von Luxburg U. A tutorial on spectral clustering // Statistics and computing. 2009. vol.17. pp. 395-416.
47. Shi J., Malik J. Normalized cuts and image segmentation // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2000. vol.22. pp. 888–905.
2. Manning C.D., Raghavan P., Sch¨utze H. Introduction to Information Retrieval // American Mathematical Society Conf. Math Challenges of the 21st Century 2000.
3. Augenlicht L. H., Kobrin D. Cloning and Screening of Sequences Expressed in a Mouse Colon Tumor // Cancer Research. 1982. vol.42. pp. 1088-1093.
4. Dash M., Liu H. Feature Selection for Classification // Intelligent Data Analysis. 1997. vol.1. pp. 131-156.
5. Jain A.K., Duin R.P.W., Jianchang M. Statistical pattern recognition: a review // Pattern Analysis and Machine Intelligence, IEEE Transactions on. 2000. vol.22. pp. 4-37.
6. Koller D., Sahami M. Toward optimal feature selection // In 13th International Conference on Machine Learning. 1995. pp. 284–292.
7. Glazko G., Coleman M., Mushegian A. Similarity searches in genome-wide numerical data sets // Biology Direct. 2006. vol.1.
8. Yan T., Ganesan D., Manmatha R. Distributed Image Search in Sensor Networks // Proceeding SenSys ’08 Proceedings of the 6th ACM conference on Embedded network sensor systems. 2008.
9. Deshpande A., Guestrin C., Madden S.R., Hellerstein J.M., Hongn W. Model-driven data acquisition in sensor networks // Proceeding VLDB ’04 Proceedings of the Thirtieth international conference on Very large data bases. 2004. vol.30. pp. 588-599.
10. Russell S.J., Norvig P., Canny J.F., Malik J.M. Edwards D.D. Artificial intelligence: a modern approach // Prentice hall Englewood Cliffs. 1995.
11. Bellman R. E. Dynamic programming // Princeton University Press. 1957.
12. Beyer K., Goldstein J., Ramakrishnan R., Shaft U. When Is Nearest Neighbor Meaningful // ICDT ’99 Proceedings of the 7th International Conference on Database Theory. 1999. pp. 217-235.
13. Hinneburg A., Aggarwal C., Keim D.A. What Is the Nearest Neighbor in High Dimensional Spaces // VLDB ’00 Proceedings of the 26th International Conference on Very Large Data Bases. 2000. pp. 506-515.
14. Kriegel H.-P., Kr¨oger P., Zimek A. Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering // ACM Transactions on Knowledge Discovery from Data. 2009. vol.3 no.3. pp. 506-515.
15. Parsons L., Haque E., Liu H. Subspace clustering for high dimensional data: a review // ACM SIGKDD Explorations Newsletter - Special issue on learning from imbalanced dataset. 2004. vol.6.
16. B¨ohm C., Berchtold S., Keim D.A. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases // ACM Computing Surveys (CSUR). 2001. no.33. vol.3.
17. Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching // Proceedings of 1984 ACM SIGMOD International Conference on Management of Data. 1984. pp. 47-57.
18. Weber R., Schek H.-J., Blott S. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces // VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases. 1998. pp. 194-205.
19. Berchtold S., Keim D. A., Kriegel H.-P. The X-tree: An Index Structure for High-Dimensional Data // VLDB ’96 Proceedings of the 22th International Conference on Very Large Data Bases. 1996. pp. 28-39.
20. Pearson K. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions // Philosophical Magazine Bases. 1901. vol.2. pp. 559-572.
21. Gunnemann S., Kremer H., Lenhard D., Seidl T. Subspace Clustering for Indexing High Dimensional Data:A Main Memory Index based on Local Reductions and Individual Multi-Representations // Proc. International Conference on Extending Database Technology. 2011. pp. 237-248.
22. M¨uller E., Assent I., G¨unnemann S., Krieger R., Seidl T. Relevant Subspace Clustering: Mining the Most Interesting Non-Redundant Concepts in High Dimensional Database // Proc. IEEE International Conference on Data Minings. 2009. pp. 377-386.
23. Assent I., Krieger R., Miller E., Seidl T. INSCY:Indexing subspace clusters with in-process-removal of redundancy // Data Mining, 2008. ICDM ’08. Eighth IEEE International Conference. 2008. pp. 719-724.
24. Assent I., Krieger R., Miller E., Seidl T. EDSC: efficient density-based subspace clustering // Proceedings of the 17th ACM conference on Information and knowledge management. 2008. pp. 1093–1102.
25. Houle M. E., Kriegel H.-P., Kr¨oger P., Schubert E., Zimek A. Can Shared- Neighbor Distances Defeat the Curse of Dimensionality? // Scientific and Statistical Database Management. 2010. pp. 482-500.
26. Strehl A., Ghosh J. Cluster ensembles — a knowledge reuse framework for combining multiple partitions // The Journal of Machine Learning Research. 2003. pp. 583-617.
27. Aggarwal C.C., Wolf J.L., Phillip S., Yu C.P., Jong S.P. Fast algorithms for projected clustering // Proceedings of the 1999 ACM SIGMOD international conference on Management of data. 1999. pp. 61–72.
28. Nagesh H., Goil S. Adaptive Grids for Clustering Massive Data Sets // SIAM International Conference on Data Mining - SDM. 2002.
29. Fan J., Fan Y., Wu Y. High-dimensional classification // World Scientific, New Jersey. 2011. pp. 3-37.
30. Silverman B. Density Estimation for Statistics and Data Analysis // Monographs on Statistics and Applied Probability, London: Chapman and Hall. 1986.
31. Huber P.J. Projection Pursuit // The Annalas of Statistics. 1985. vol.2. no.13. pp. 435—475.
32. Friedman J.H. Exploratory projection pursuit // Journal of American Statistical Association. 1987. no.82. pp. 249—266.
33. Dobkin D., Lipton R.J. Multidimensional Searching Problems // SIAM Journal on Computing. 1974. no.5. pp. 181–186.
34. Meiser S. Point location in arrangemenm of hyperplanes // Information and Computation. 1993. no.106. pp. 286–303.
35. Andoni A., Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions // Communications of the ACM - 50th anniversary issue. 2008. vol.51. pp. 117-122.
36. Indyk P., Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998. pp. 604-613.
37. Datar M., Immorlica N., Indyk P., Mirrokni V.S. Locality-sensitive hashing scheme based on p-stable distributions // Proceedings of the twentieth annual symposium on Computational geometry. 2004. pp. 253-262.
38. Deegalla S., Bostrom H. Reducing High-Dimensional Data by Principal Component Analysis vs. Random Projection for Nearest Neighbor Classification // Proceedings of the 5th International Conference on Machine Learning and Applications. 2006. pp. 245-250.
39. Ian J. Principal component analysis // Wiley Online Library. 2005.
40. Gorban A. N. Principal manifolds for data visualization and dimension reduction // Springer. 2007. vol.58.
41. Tenenbaum J.B., De Silva V., Langford J.C. A global geometric framework for nonlinear dimensionality reduction // Science. 2000. vol.290. no.5500. pp. 2319–2323.
42. Kruskal J.B. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis // Psychometrika. 1964. vol.29. no.1. pp. 1-27.
43. Cox T.F., Cox M.A.A. Multidimensional scaling // CRC Press. 2010.
44. Heisterkamp D.R., Peng J. Kernel VA-files for relevance feedback retrieval // Proceedings of the 1st ACM international workshop on Multimedia databases. 2003. pp. 48-54.
45. Heisterkamp D.R., Peng J. Sparse subspace clustering // IEEE Conference on Computer Vision and Pattern Recognition CVPR 2009. 2009. pp. 2790-2797.
46. Von Luxburg U. A tutorial on spectral clustering // Statistics and computing. 2009. vol.17. pp. 395-416.
47. Shi J., Malik J. Normalized cuts and image segmentation // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2000. vol.22. pp. 888–905.
Data Indexing in High Dimensional Space
Abstract
Indexing of the data is an essential part of the search problem. Whilst a well studied set of efficient algorithms of indexing and search exist for a data in the spaces of the dimensionality less then 5, these algorithms are inefficient or not applicable for high dimensional spaces. We review existing studies of the problems related to indexing in a high dimensional space for a nearest neighbour search problem. Possible methods of the designated problems solution that are applicable in the areas of data analysis such as clustering and hidden structure elicitation are regarded. The question on the applicability of the various dimensional reduction methods for an indexing and nearest neighbour search problem.
Опубликован
2014-06-02
Как цитировать
Новиков, Б. А., & Судос, И. В. (2014). Индексирование данных в пространстве большой размерности. Труды СПИИРАН, 2(33), 24-47. https://doi.org/10.15622/sp.33.2
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
