High-Dimensional Indexing: Transformational Approaches to High-Dimensional Range and Similarity Searches

در این مونوگرافی، مشکل نمایه سازی با ابعاد بالا را مطالعه می کنیم و به طور سیستماتیک دو ساختار شاخص کارآمد را معرفی می کنیم: یکی برای پرس و جوهای محدوده و دیگری برای پرس و جوهای شباهت. آزمایش‌ها و مطالعات مقایسه‌ای گسترده برای نشان دادن برتری روش‌های نمایه‌سازی پیشنهادی انجام می‌شود.
بسیاری از برنامه‌های کاربردی پایگاه داده جدید، مانند پایگاه‌های اطلاعاتی چندرسانه‌ای یا سیستم‌های اطلاعات قیمت سهام، ویژگی‌ها یا ویژگی‌های مهم اشیاء داده را به نقاط با ابعاد بالا تبدیل می‌کنند. بنابراین جستجو برای اشیا بر اساس این ویژگی ها جستجوی نقاط در این فضای ویژگی است. برای پشتیبانی از بازیابی کارآمد در چنین پایگاه‌های داده با ابعاد بالا، فهرست‌ها برای هرس فضای جستجو مورد نیاز هستند. شاخص‌های پایگاه‌های داده کم‌بعد به خوبی مورد مطالعه قرار گرفته‌اند، در حالی که بیشتر این فهرست‌های ویژه برنامه‌ها با تعداد ابعاد مقیاس‌پذیر نیستند، و برای پشتیبانی از جستجوهای مشابه و اتصالات با ابعاد بالا طراحی نشده‌اند.

In this monograph, we study the problem of high-dimensional indexing and systematically introduce two efficient index structures: one for range queries and the other for similarity queries. Extensive experiments and comparison studies are conducted to demonstrate the superiority of the proposed indexing methods.
Many new database applications, such as multimedia databases or stock price information systems, transform important features or properties of data objects into high-dimensional points. Searching for objects based on these features is thus a search of points in this feature space. To support efficient retrieval in such high-dimensional databases, indexes are required to prune the search space. Indexes for low-dimensional databases are well studied, whereas most of these application specific indexes are not scaleable with the number of dimensions, and they are not designed to support similarity searches and high-dimensional joins.