?
Cross-Document Pattern Matching
P. 196–207.
Kucherov G., Nekrich Y., Стариковская Т. А.
We study a new variant of the string matching problem called {\em cross-document string matching}, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear-space solutions are proposed with query time bounds that either do not depend at all on the pattern size or depend on it in a very limited way (doubly logarithmic). As a side result, we propose an improved solution to the {\em weighted level ancestor} problem.
Язык:
английский
В книге
Vol. 7354: Proceedings of the 23rd Symposium on Combinatorial Pattern Matching. , Berlin: Springer, 2012.
Рубцов А. А., Вялый М. Н., , in: Descriptional Complexity of Formal Systems: 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings.: Springer, 2021. P. 150–162.
Добавлено: 2 февраля 2022 г.
Springer, 2019.
Добавлено: 26 октября 2021 г.
Фомичев М. И., Ульянов М. В., Информационные технологии 2018 Т. 24 № 11 С. 698–704
Повышение временной эффективности программных реализаций метода ветвей и границ для асимметричной задачи коммивояжера может быть достигнуто как за счет выбора наиболее приемлемой структуры данных, обеспечивающей эффективные по времени операции с листьями поискового дерева решений, так и за счет использования дополнительной памяти для хранения усеченных матриц в листьях поискового дерева решений. Дополнительно могут быть предложены и ...
Добавлено: 26 января 2020 г.
Бабенко М. А., Колесниченко И. И., Smirnov I., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 637–646
Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an “optimal” extract-min operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the minimum. Extracting all elements faster is impossible as ...
Добавлено: 6 декабря 2019 г.
Springer, 2019.
Добавлено: 4 августа 2019 г.
Галимуллин М. Ф., Калишенко Е. Л., Рапоткин Н. А., Известия Санкт-Петербургского государственного электротехнического университета ЛЭТИ 2016 № 7 С. 13–23
Рассматриваются некоторые сценарии использования конкурентных структур данных, показывающие повышение производительности при увеличении времени работы одного потока, которому остальные потоки делегируют свои задачи. Данный подход получил название flat-combining (FC) [1]. Представлены несколько разработанных стратегий синхронизации, описаны их преимущества и область применения. ...
Добавлено: 1 ноября 2018 г.
Бабкина Т. С., Демидовский А. В., Бабкин Э. А., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143–155
В этой работе представлены два новых подхода к решению классической NP-трудной задачи по поиску максимальной клики. Эта задача, которая часто возникает в области управления информацией, включая проектирование структур баз данных и обработку больших объемов данных. В нашем исследовании мы фокусируемся на решении этой задачи с использованием парадигмы искусственных нейронных сетей. Первый подход объединяет парадигму искусственных нейро-сетей и ...
Добавлено: 3 октября 2018 г.
Berlin, Heidelberg: Springer, 2017.
The 12th issue of LNCS Transactions on Petri Nets and Other Models of Concurrency (ToPNoC) contains revised and extended versions of a selection of the best papers from the workshops held at the 37th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets 2016, Toruń, Poland, 19–24 June 2016), and the ...
Добавлено: 27 сентября 2017 г.
Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38–46
Добавлено: 5 ноября 2016 г.
Maxim Babenko, Gawrychowski P., Kociumaka T. и др., Theoretical Computer Science 2016 Vol. 638 P. 112–121
We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length . n. For the minimal suffix problem we show that for every . τ, . 1≤τ≤logn, there exists a linear-space data structure with . O(τ) query time and . O(nlogn/τ) preprocessing time. As a ...
Добавлено: 8 октября 2015 г.
Таганрог: Издательство ЮФУ, 2015.
Сборник составлен по материалам VI Международной научно-практической конференции "Технологии разработки информационных систем", состоявшейся 6-12 сентабря 2015 г. в г. Геленджик.
Ответственность за аутентичность и точность цитат, имен, названий и иных сведений несут авторы публикуемых материалов. Материалы публикуются в авторской редакции.
Мероприятие проведено при финансовой поддержке Российского фонда фундаментальных исследований (грант № 15-07-20559-г). ...
Добавлено: 13 сентября 2015 г.
Бабенко М. А., Gawrychowski P., Kociumaka T. и др., , in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.: San Diego: SIAM, 2015. P. 572–591.
We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size ω ≤ n, our method builds the wavelet tree in O(n log ω √log n) time, improving upon the state-of-the-art algorithm ...
Добавлено: 4 октября 2014 г.
Vildhoj H. W., Стариковская Т. А., , in: Combinatorial Algorithms. 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected PapersVol. 8986.: Springer, 2014. P. 338–350.
In this paper we study the structure of suffix trees. Given an unlabeled tree τ on n nodes and suffix links of its internal nodes, we ask the question “Is τ a suffix tree?”, i.e., is there a string S whose suffix tree has the same topological structure as τ? We place no restrictions on ...
Добавлено: 4 октября 2014 г.
Springer, 2014.
This book constitutes the proceedings of the 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014, held in Ouro Preto, Brazil, in October 2014. The 20 full and 6 short papers included in this volume were carefully reviewed and selected from 45 submissions. The papers focus not only on fundamental algorithms in string ...
Добавлено: 4 октября 2014 г.
Babenko A., Lempitsky V., , in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2012).: Providence: IEEE, 2012. P. 3069–3076.
Добавлено: 1 октября 2014 г.
Пономаренко А. А., В кн.: Труды 38-й конференции "Информационные технологии и системы - 2014".: Н. Новгород: ИППИ РАН, 2014. С. 194–200.
Классическим подходом к организации информации для последующего быстрого поиска является построение индекса. Однако этот подход имеет несколько недостатков. Индекс необходимо перестраивать и поддерживать в актуальном виде, что затруднительно в случае разрозненной информации, такой как текстовая информация в WEB. Эти недостатки являются следствием того, что индекс является реорганизованной копией индексируемой информации. В данной работе предлагается способ ...
Добавлено: 10 сентября 2014 г.
Бабенко М. А., Стариковская Т. А., , in: Lecture Notes in Computer ScienceVol. 5010: Proceedings of the Third International Computer Science Symposium in Russia.: Berlin: Springer, 2008. P. 64–75.
Given a set of $N$ strings $A = \set{\alpha_1, \ldots, \alpha_N}$ of total length $n$ over alphabet~$\Sigma$ one may ask to find, for a fixed integer $K$, $2 \le K \le N$, the longest substring $\beta$ that appears in at least $K$ strings in $A$. It is known that this problem can be solved in ...
Добавлено: 30 октября 2013 г.