Multidimensional matching and fast search in suffix trees

Name: Work Video:
Duration: 3 min 30 s
Description: We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. Using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension.
Richard Cole; Moshe Lewenstein
{'id': 'https://openalex.org/W1993696469', 'doi': 'https://doi.org/10.5555/644108.644251', 'title': 'Multidimensional matching and fast search in suffix trees', 'display_name': 'Multidimensional matching and fast search in suffix trees', 'publication_year': 2003, 'publication_date': '2003-01-12', 'ids': {'openalex': 'https://openalex.org/W1993696469', 'doi': 'https://doi.org/10.5555/644108.644251', 'mag': '1993696469'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://dblp.uni-trier.de/db/conf/soda/soda2003.html#ColeL03', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': [], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5042866153', 'display_name': 'Richard Cole', 'orcid': 'https://orcid.org/0000-0002-5885-0222'}, 'institutions': [], 'countries': [], 'is_corresponding': False, 'raw_author_name': 'Richard Cole', 'raw_affiliation_strings': [], 'affiliations': []}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5012404981', 'display_name': 'Moshe Lewenstein', 'orcid': 'https://orcid.org/0000-0002-8272-244X'}, 'institutions': [{'id': 'https://openalex.org/I13955877', 'display_name': 'Bar-Ilan University', 'ror': 'https://ror.org/03kgsv495', 'country_code': 'IL', 'type': 'education', 'lineage': ['https://openalex.org/I13955877']}], 'countries': ['IL'], 'is_corresponding': False, 'raw_author_name': 'Moshe Lewenstein', 'raw_affiliation_strings': ['Bar Ilan University ,'], 'affiliations': [{'raw_affiliation_string': 'Bar Ilan University ,', 'institution_ids': ['https://openalex.org/I13955877']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 0.233, 'has_fulltext': False, 'cited_by_count': 3, 'citation_normalized_percentile': {'value': 0.404222, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 70, 'max': 72}, 'biblio': {'volume': None, 'issue': None, 'first_page': '851', 'last_page': '852'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T11269', 'display_name': 'Algorithms and Data Compression', 'score': 1.0, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T11269', 'display_name': 'Algorithms and Data Compression', 'score': 1.0, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T12326', 'display_name': 'Network Packet Processing and Optimization', 'score': 0.9914, 'subfield': {'id': 'https://openalex.org/subfields/1708', 'display_name': 'Hardware and Architecture'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T12029', 'display_name': 'DNA and Biological Computing', 'score': 0.9875, 'subfield': {'id': 'https://openalex.org/subfields/1312', 'display_name': 'Molecular Biology'}, 'field': {'id': 'https://openalex.org/fields/13', 'display_name': 'Biochemistry, Genetics and Molecular Biology'}, 'domain': {'id': 'https://openalex.org/domains/1', 'display_name': 'Life Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/generalized-suffix-tree', 'display_name': 'Generalized suffix tree', 'score': 0.93245184}, {'id': 'https://openalex.org/keywords/compressed-suffix-array', 'display_name': 'Compressed suffix array', 'score': 0.9142722}], 'concepts': [{'id': 'https://openalex.org/C118146561', 'wikidata': 'https://www.wikidata.org/wiki/Q5532514', 'display_name': 'Generalized suffix tree', 'level': 4, 'score': 0.93245184}, {'id': 'https://openalex.org/C100903775', 'wikidata': 'https://www.wikidata.org/wiki/Q5157028', 'display_name': 'Compressed suffix array', 'level': 4, 'score': 0.9142722}, {'id': 'https://openalex.org/C2781166958', 'wikidata': 'https://www.wikidata.org/wiki/Q1426863', 'display_name': 'Suffix tree', 'level': 3, 'score': 0.89502895}, {'id': 'https://openalex.org/C2779804580', 'wikidata': 'https://www.wikidata.org/wiki/Q102047', 'display_name': 'Suffix', 'level': 2, 'score': 0.8595139}, {'id': 'https://openalex.org/C111696304', 'wikidata': 'https://www.wikidata.org/wiki/Q2303697', 'display_name': 'Sorting', 'level': 2, 'score': 0.5874128}, {'id': 'https://openalex.org/C7757238', 'wikidata': 'https://www.wikidata.org/wiki/Q374040', 'display_name': 'String searching algorithm', 'level': 3, 'score': 0.5493894}, {'id': 'https://openalex.org/C311688', 'wikidata': 'https://www.wikidata.org/wiki/Q2393193', 'display_name': 'Time complexity', 'level': 2, 'score': 0.5269595}, {'id': 'https://openalex.org/C165064840', 'wikidata': 'https://www.wikidata.org/wiki/Q1321061', 'display_name': 'Matching (statistics)', 'level': 2, 'score': 0.51065046}, {'id': 'https://openalex.org/C112876837', 'wikidata': 'https://www.wikidata.org/wiki/Q837518', 'display_name': 'Alphabet', 'level': 2, 'score': 0.5103175}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.49931598}, {'id': 'https://openalex.org/C68859911', 'wikidata': 'https://www.wikidata.org/wiki/Q1503724', 'display_name': 'Pattern matching', 'level': 2, 'score': 0.49292374}, {'id': 'https://openalex.org/C33676613', 'wikidata': 'https://www.wikidata.org/wiki/Q13415176', 'display_name': 'Dimension (graph theory)', 'level': 2, 'score': 0.48141432}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.46844962}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.4253714}, {'id': 'https://openalex.org/C157486923', 'wikidata': 'https://www.wikidata.org/wiki/Q1376436', 'display_name': 'String (physics)', 'level': 2, 'score': 0.41364208}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.32431084}, {'id': 'https://openalex.org/C154945302', 'wikidata': 'https://www.wikidata.org/wiki/Q11660', 'display_name': 'Artificial intelligence', 'level': 1, 'score': 0.21345547}, {'id': 'https://openalex.org/C105795698', 'wikidata': 'https://www.wikidata.org/wiki/Q12483', 'display_name': 'Statistics', 'level': 1, 'score': 0.10584813}, {'id': 'https://openalex.org/C41895202', 'wikidata': 'https://www.wikidata.org/wiki/Q8162', 'display_name': 'Linguistics', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C138885662', 'wikidata': 'https://www.wikidata.org/wiki/Q5891', 'display_name': 'Philosophy', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C37914503', 'wikidata': 'https://www.wikidata.org/wiki/Q156495', 'display_name': 'Mathematical physics', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://dblp.uni-trier.de/db/conf/soda/soda2003.html#ColeL03', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 8, 'referenced_works': ['https://openalex.org/W1984398316', 'https://openalex.org/W2026024229', 'https://openalex.org/W2085917651', 'https://openalex.org/W2092215082', 'https://openalex.org/W2107079154', 'https://openalex.org/W2121252285', 'https://openalex.org/W2533248932', 'https://openalex.org/W2610179052'], 'related_works': ['https://openalex.org/W3113848129', 'https://openalex.org/W2964320652', 'https://openalex.org/W2732093072', 'https://openalex.org/W2592203046', 'https://openalex.org/W2403955627', 'https://openalex.org/W2360372990', 'https://openalex.org/W2355168454', 'https://openalex.org/W2345086198', 'https://openalex.org/W2287432258', 'https://openalex.org/W2102467481', 'https://openalex.org/W2086285277', 'https://openalex.org/W2082932857', 'https://openalex.org/W2051533549', 'https://openalex.org/W1963887925', 'https://openalex.org/W1882920571', 'https://openalex.org/W1868629800', 'https://openalex.org/W185321349', 'https://openalex.org/W1573352354', 'https://openalex.org/W1554611468', 'https://openalex.org/W1543802159'], 'abstract_inverted_index': {'We': [0], 'show': [1], 'how': [2], 'to': [3], 'construct': [4], 'a': [5, 9, 25], 'suffix': [6, 47, 51, 54], 'tree': [7], 'of': [8, 37, 46], 'text': [10], 'string': [11], 't': [12], 'in': [13, 20, 65], 'linear': [14, 59], 'time,': [15], 'after': [16], 'sorting': [17], 'the': [18, 21, 38, 43], 'characters': [19], 'text,': [22], 'so': [23], 'that': [24], 'search': [26], 'for': [27, 62], 'pattern': [28, 63], 'p': [29], 'take': [30], 'time': [31, 60], 'O(p': [32], '+': [33], 'log': [34], 't),': [35], 'independent': [36], 'alphabet': [39], 'size,': [40], 'thereby': [41], 'matching': [42, 64], 'asymptotic': [44], 'performance': [45], 'arrays.': [48], 'Using': [49], 'these': [50], 'trees': [52], 'or': [53], 'arrays': [55], 'we': [56], 'then': [57], 'give': [58], 'algorithms': [61], 'any': [66], 'fixed': [67], 'dimension.': [68]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W1993696469', 'counts_by_year': [{'year': 2014, 'cited_by_count': 2}], 'updated_date': '2024-12-14T05:14:18.512492', 'created_date': '2016-06-24'}
Publication Information

Basic Information

Access and Citation

AI Researcher Chatbot

Primary Location

Authors

Topics

Keywords

Related Works
