When integrating data from autonomous sources, exact matches of items that represent the same real-world object often fail due to a lack common keys. Yet in many cases structural information is available and can be used match such data. Typically matching must approximate since representations sources differ. We propose pq -grams approximately hierarchical define -gram distance between ordered labeled trees as an effective efficient approximation fanout weighted tree edit distance. prove...

Abstract In this paper, we investigate the computation of alternative paths between two locations in a road network. More specifically, study k-shortest with limited overlap ( $$k\text {SPwLO}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mtext>SPwLO</mml:mtext> </mml:mrow> </mml:math> ) problem that aims at finding set k such all are sufficiently dissimilar to each other and as short possible. To compute queries, propose exact algorithms,...

Abstract Temporal information plays a crucial role in many database applications, however support for queries on such data is limited. We present an index structure, termed RD-index , to range-duration over interval timestamped relations, which constrain both the range of tuples’ positions timeline and their duration . grid structure two-dimensional space, representing position timestamps, respectively. Instead using regular grid, we consider distribution construction order ensure that each...

When integrating data from autonomous sources, exact matches of items that represent the same real world object often fail due to a lack common keys. Yet in many cases structural information is available and can be used match such data. As running example we use residential address information. Addresses are hierarchical structures present databases. Often they best, if not only, relationship between sources. Typically matching has approximate since representations sources differ.We propose...

Each tuple in a valid-time relation includes an interval attribute T that represents the tuple's valid time. The overlap join between two relations determines all pairs of tuples with overlapping intervals. Although joins are common, existing partitioning and indexing schemes inefficient if data long-lived or intervals intersect partition boundaries.

In order to process interval timestamped data, the sequenced semantics has been proposed. This paper presents a relational algebra solution that provides native support for three properties of semantics: snapshot reducibility, extended and change preservation. We introduce two temporal primitives, splitter aligner, define rules use these primitives reduce operators their nontemporal counterparts. Our supports through adjustment timestamp propagation. have implemented reduction in kernel...

The new sequencing technologies enable to scan very long and dense genetic sequences, obtaining datasets of markers that are an order magnitude larger than previously available. Such sequences characterized by common alleles interspersed with multiple rarer alleles. This situation has renewed the interest for identification haplotypes carrying rare risk However, large scale explorations linkage-disequilibrium (LD) pattern identify haplotype blocks not easy perform, because traditional...

Shortest path computation is a fundamental problem in road networks with application various domains research and industry. However, returning only the shortest often not satisfying; users are also interested alternative paths which might be longer but have other advantages, e.g., less frequent traffic congestion. In this paper, we formally introduce k-Shortest Paths Limited Overlap (k-SPwLO) seeking to recommend k (a) as short possible (b) sufficiently dissimilar based on user-controlled...

We propose a more realistic approach to trip planning for tourist applications by adding category information points of interest (POIs). This makes it easier tourists formulate their preferences stating constraints on categories rather than individual POIs. However, solving this problem is not just matter extending existing algorithms. In our we exploit the fact that POIs are usually evenly distributed but tend appear in clusters. develop group efficient algorithms based clustering with...

Many databases contain temporal, or time-referenced, data and use intervals to capture the temporal aspect. While SQL-based database management systems (DBMSs) are capable of supporting interval data, support they offer can be improved considerably. A range proposed models query languages ample evidence this effect. Natural queries that very difficult formulate in SQL easy these languages. The increased focus on analytics over historical where generally more complex exacerbates difficulties...

The problem of deriving lower and upper bounds for the edit distance between undirected, labeled graphs has recently received increasing attention. However, only one algorithm been proposed that allegedly computes not an but also a bound non-uniform costs incorporates information about both node edge labels. In this paper, we demonstrate is incorrect. We present corrected version BRANCH runs in O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML"...

Intelligent Educational Systems (IESs) need large amounts of educational content that is typically not provided by the creators these systems. In this paper we discuss a new approach for authoring practical IESs where core done professional design teams, while mainly developed teachers who use system in their classes. The major bottleneck lack intelligent support tools allow regular to author an IES needs order perform its functions. As contribution solving problem, present our recent work...

In data integration applications, a join matches elements that are common to two sources. Often, however, represented slightly different in each source, so an approximate must be used. For XML data, most strategies based on some ordered tree matching technique. But data-centric the order is irrelevant: should match even if their subelement varies. this paper we give solution for of unordered trees. Our windowed pq-grams. We develop efficient technique systematically generate pq-grams...

Time series data is ubiquitous but often incomplete, e.g., due to sensor failures and transmission errors. Since many applications require complete data, missing values must be imputed before further processing possible. We propose Top-k Case Matching (TKCM) impute in streams of time data. TKCM defines for each a set reference exploits similar historical situations the imputation. A situation characterized by anchor point pattern that consists l consecutive measurements over series. value s...

Isochrones are defined as the set of all points from which a specific point interest is reachable within given time span. This demo paper presents solution to compute isochrones in multi-modal, schedule-based transport networks. The system implemented Java on top Oracle Spatial Network Model and deployed at Municipality Bolzano-Bozen planning instrument.

The manual acquisition of terminological material from the domain-specific text is a very time-consuming task. Recent advances in text-processing research provide basis for automating this Computer-assisted term improves both quantity and quality work. This paper gives brief overview new approach terminology acquisition. Three subtasks are distinguished: compilation an electronic corpus, extraction data, management data. Each will be discussed some detail by identifying core problems as well...