NDLI: Accelerating sequence searching: dimensionality reduction method

Content Provider	Springer Nature Link
Author	Song, Guojie Cui, Bin Zheng, Baihua Xie, Kunqing Yang, Dongqing
Copyright Year	2008
Abstract	Similarity search over long sequence dataset becomes increasingly popular in many emerging applications, such as text retrieval, genetic sequences exploring, etc. In this paper, a novel index structure, namely Sequence Embedding Multiset tree (SEM − tree), has been proposed to speed up the searching process over long sequences. The SEM-tree is a multi-level structure where each level represents the sequence data with different compression level of multiset, and the length of multiset increases towards the leaf level which contains original sequences. The multisets, obtained using sequence embedding algorithms, have the desirable property that they do not need to keep the character order in the sequence, i.e. shorter representation, but can reserve the majority of distance information of sequences. Each level of the tree serves to prune the search space more efficiently as the multisets utilize the predicability to finish the searching process beforehand and reduce the computational cost greatly. A set of comprehensive experiments are conducted to evaluate the performance of the SEM-tree, and the experimental results show that the proposed method is much more efficient than existing representative methods.
Starting Page	301
Ending Page	322
Page Count	22
File Format	PDF
ISSN	02191377
Journal	Knowledge and Information Systems
Volume Number	20
Issue Number	3
e-ISSN	02193116
Language	English
Publisher	Springer-Verlag
Publisher Date	2008-12-12
Publisher Place	London
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Sequence similarity search Sequence embedding Index Dimension reduction Business Information Systems Information Systems and Communication Service
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Information Systems Human-Computer Interaction Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Effectiveness of NAQ-tree as index structure for similarity search in high-dimensional metric space

Indexing expensive functions for efficient multi-dimensional similarity search

A compact multi-resolution index for variable length queries in time series databases

Distance approximation techniques to reduce the dimensionality for multimedia databases

Transfer dimensionality reduction by Gaussian process in parallel

Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

Continuous similarity search for evolving queries

A geometrical solution to time series searching invariant to shifting and scaling

Similarity measures for OLAP sessions

Accelerating sequence searching: dimensionality reduction method

Similar Documents

Effectiveness of NAQ-tree as index structure for similarity search in high-dimensional metric space

Indexing expensive functions for efficient multi-dimensional similarity search

A compact multi-resolution index for variable length queries in time series databases

Distance approximation techniques to reduce the dimensionality for multimedia databases

Transfer dimensionality reduction by Gaussian process in parallel

Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

Continuous similarity search for evolving queries

A geometrical solution to time series searching invariant to shifting and scaling

Similarity measures for OLAP sessions

Accelerating sequence searching: dimensionality reduction method