کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4945099 1438293 2017 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Compressed representation of dynamic binary relations with applications
ترجمه فارسی عنوان
نمایش فشرده روابط پویا دودویی با برنامه های کاربردی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی
We introduce a dynamic data structure for the compact representation of binary relations R⊆A×B. The data structure is a dynamic variant of the k2-tree, a static compact representation that takes advantage of clustering in the binary relation to achieve compression. Our structure can efficiently check whether two objects (a, b) ∈ A × B are related, and list the objects of B related to some a ∈ A and vice versa. Additionally, our structure allows inserting and deleting pairs (a, b) in the relation, as well as modifying the base sets A and B. We test our dynamic data structure in different contexts, including the representation of Web graphs and RDF databases. Our experiments show that our dynamic data structure achieves good compression ratios and fast query times, close to those of a static representation, while also providing efficient support for updates in the represented binary relation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Systems - Volume 69, September 2017, Pages 106-123
نویسندگان
, , , ,