10.14489/vkit.2014.12.pp.048-055

DOI: 10.14489/vkit.2014.12.pp.048-055

Аверченков В. И., Гулаков В. К., Трубаков А. О., Трубаков Е. О., Матюшин В. Н.
АНАЛИЗ И НЕКОТОРАЯ КЛАССИФИКАЦИЯ МЕТОДОВ ДОСТУПА К ДАННЫМ
(с. 48-55)

Аннотация. Рассмотрены некоторые общие принципы классификации методов доступа к различным группам данных. В рамках каждой группы показаны соответствующие структуры данных, позволяющие проводить их эффективную обработку. Даны описания отличительных особенностей структур данных, соответствующих различным методам доступа, достижений и проблем в их применении.

Ключевые слова: одномерные, многомерные, метрические, пространственно-временные методы доступа; методы доступа к данным большой размерности; структуры данных; индексирование исторических, текущих и будущих данных; контекстно-зависимое хеширование.

Averchenkov V. I., Gulakov V. K., Trubakov A. О., Trubakov E. O., Matyushin V. N.
ANALYSIS AND CLASSIFICATION OF DATA ACCESS METHODS
(pp. 48-55)

Abstract. Different types of data and search queries require effective methods of information retrieval. However, there is no well-known and established classification of such methods and data structures, because the area of research is quite new and its terminology and methods continue to evolve. The lack of systematization and practical recommendations makes it hard to choose the best search method and also does not allow to figure out evident drawbacks of the search methods and to develop new solutions. In this paper the authors present their own classification based upon the analysis of the available works. The authors do not claim it to be accurate or the only possible one, but rather reflect their own experience of working with various information retrieval and indexing methods. This article consists of five sections, with each section discussing its own group of data access methods (one-dimensional, multi-dimensional, metric, high dimensional, and temporal). Current state of research, key methods and algorithms and their features with the strong influence on the performance are described for each group of methods. The authors provide an overview of downsides inherent to all presented kinds of algorithms, as well as pros and cons of the basic approaches.Special attention is given to the analysis of the spatial, temporal-spatial and metric indexing methods, which have been actively studied and developed during the last years. The authors present classification features and scheme which makes the description more illustrative and understandable. The paper contains a lot of references which is helpful for studying the topic more closely.

Keywords: One-dimensional, multi-dimensional, metric, spatio-temporal access methods; Methods of data access high-dimensional; Data structures; Indexing historical, present and future data; Context-sensitive hashing.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

В. И. Аверченков, В. К. Гулаков, А. О. Трубаков, Е. О. Трубаков, В. Н. Матюшин (Брянский государственный технический университет) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

V. I. Averchenkov, V. K. Gulakov, A. О. Trubakov, E. O. Trubakov, V. N. Matyushin (Bryansk State Technical University) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Гулаков В. К., Трубаков А. О. Многомерные структуры данных. Брянск: Изд-во БГТУ, 2010. 387 с.
2. Samet H. The Applications of Spatial Data Struc-tures: Computer Graphics, Image Processing, and GIS. Reading, MA: Addison-Wesley, 1990. 512 p.
3. Seeger B., Kriegel H.-P. The Buddy Tree: An Effi-cient and Robust Access Method for Spatial Data Base Sys-tems // Proc. 16th Intern. Conf. on Very Large Data Bases. Brisbane, Australia. 1990. P. 590 – 601.
4. Gaede V., Günther O. Multidimensional Access Methods // ACM Computing Surveys. 1998. V. 30, № 2. P. 170 – 231.
5. Mokbel M. F., Ghanem T. M., Aref W. G. Spatio-Temporal Access Methods // IEEE Data Engineering Bul¬letin. 2003. № 26(2). P. 40 – 49.
6. Brin S. Near Neighbor Search in Large Metric Spaces // VLDB’95 Proc. of the 21th Intern. Conf. on Very Large Data Bases. Zurich, Switzerland. 1995. P. 574 – 584.
7. Гулаков В. К., Матюшин В. Н. Оценка эффек-тивности использования метрических деревьев в при-ближенном поиске на основе обобщенного гиперплоско-стного разбиения множества объектов // Вестник БГТУ. 2013. № 4(40). С. 106 – 112.
8. Searching in Metric Spaces / E. Chavez, G. Navarro, R. Baeza-Yates, J. Marroquin // ACM Computing Surveys. 2001. V. 33, № 3. P. 273 – 321.
9. Yi B.-K., Faloutsos C. Fast Time Sequence Index-ing for Arbitrary Lp Norms // VLDB’00 Proc. of the 26th Intern. Conf. on Very Large Data Bases. Cairo, Egypt. 2000. P. 385 – 394.
10. Onishi K., Tokai U. T., Kobayakawa M., Hoshi M. mm-GNAT: Index Structure for Arbitrary Lp Norm // The 2nd IEEE Intern. Workshop on Multimedia Databases and Data Management (IEEE-MDDM). 2007. P. 117 – 126.
11. Chakrabarti K. Managing Large Multidimensional Datasets Inside a Database System. Phd Thesis, University of Illinois at Urbana-Champaign. Urbana, Illinois, 2001. 239 p.
12. Moënne-Loccoz N. High-Dimensional Access Methods for Efficient Similarity Queries. Technical Report 05.05. University of Geneva. Computer Vision and Multime-dia Laboratory. 2005.
13. Markov Kr. Multi-Domain Information Model // Information Theories and Applications. 2004. V. 11, № 4. P. 303 – 308.
14. Гулаков В. К., Трубаков А. О., Трубаков Е. О. Пространственно-временные структуры данных. Брянск: Изд-во БГТУ, 2013. 214 с.
15. Uhlmann J. K. Satisfying General Proximity /Similarity Queries with Metric Trees // Information Proc. Letters. 1991. V. 40, № 4. P. 175 – 179.
16. Formation of the Color Palette for Content Based Image Retrieval Automated Systems / V. I. Averchenkov et al. // World Applied Sciences Journal 24 (Information Technologies in Morden Industry, Education & Society). 2013. V. 1, № 6. P. 1 – 6.
17. On Multidimensional Data and Modern Disks / S. W. Schlosser et al. // Proc. of the 4th USENIX Conference on File and Storage Technology (FAST’05). San Francisco, CA. 2005. P. 13 – 16.

Eng

1. Gulakov V. K., Trubakov A. O. (2010). Multidimen-sional data structures. Briansk: Izdatel'stvo BGTU.
2. Samet H. (1990). The applications of spatial data structures: Computer graphics, image processing, and GIS. Reading, MA: Addison-Wesley.
3. Seeger B., Kriegel H.-P. (1990). The Buddy Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. Proc. 16th International Conference on Very Large Data Bases. Brisbane, Australia, pp. 590-601.
4. Gaede V., Günther O. (1998). Multidimensional ac-cess methods. ACM Computing Surveys, 30(2), pp. 170-231.
5. Mokbel M. F., Ghanem T. M., Aref W. G. (2003). Spatio-temporal access methods. IEEE Data Engineering Bulletin, 26(2), pp. 40-49.
6. Brin S. (1995). Near Neighbor Search in Large Met-ric Spaces. VLDB’95 Proc. of the 21th International Confer-ence on Very Large Data Bases. Zurich, Switzerland, pp. 574-584.
7. Gulakov V. K., Matiushin V. N. (2013). Evaluation of the effectiveness of the use of metric trees in approximate search based on the generalized hyperplane partitioning the set of objects. Vestnik BGTU, 40(4), pp. 106-112.
8. Chavez E., Navarro G., Baeza-Yates R., Marroquin J. (2001). Searching in metric spaces. ACM Computing Sur-veys, 33(3), pp. 273-321. doi: 10.1145/502807.502808
9. Yi B.-K., Faloutsos C. (2000). Fast Time Sequence Indexing for Arbitrary Lp Norms. VLDB’00 Proc. of the 26th International Conference on Very Large Data Bases. Cairo, Egypt, pp. 385-394.
10. Onishi K., Tokai U. T., Kobayakawa M., Hoshi M. (2007). mm-GNAT: Index Structure for Arbitrary Lp Norm. The 2nd IEEE International Workshop on Multimedia Data-bases and Data Management (IEEE-MDDM), pp. 117-126.
11. Chakrabarti K. (2001). Managing Large Multidi-mensional Datasets Inside a Database System. Phd Thesis, University of Illinois at Urbana-Champaign. Urbana, Illinois.
12. Moënne-Loccoz N. (2005). High-Dimensional Ac-cess Methods for Efficient Similarity Queries. Technical Re-port 05.05. University of Geneva. Computer Vision and Mul-timedia Laboratory.
13. Markov Kr. (2004). Multi-domain information mod-el. Information Theories and Applications, 11(4), pp. 303-308.
14. Gulakov V. K., Trubakov A. O., Trubakov E. O. (2013). Spatio-temporal data structures. Briansk: Izdatel'stvo BGTU.
15. Uhlmann J. K. (1991). Satisfying general proximity. Similarity queries with metric trees. Information Proc. Let-ters, 40(4), pp. 175-179.
16. Averchenkov V. I. et al. (2013). Formation of the color palette for content based image retrieval automated systems. World Applied Sciences Journal 24 (Information Technologies in Morden Industry, Education & Socie-ty), 1(6), pp. 1-6.
17. Schlosser S. W. et al. (2005). On Multidimensional Data and Modern Disks. Proc. of the 4th USENIX Confer-ence on File and Storage Technology (FAST’05). San Fran-cisco, CA, pp. 13-16.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 250 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2014.12.pp.048-055}

Eng

This article is available in electronic format (PDF).

The cost of a single article is 250 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2014.12.pp.048-055}