Structural Comparison of Labelled Graph Data

标记图数据的结构比较

• 批准号: EP/G012407/1
• 负责人: Richard Connor
• 金额: $ 10.33万
• 依托单位: University of Strathclyde
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2009
• 资助国家: 英国
• 起止时间: 2009 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FG012407%2F1
• 关键词: Structural; Comparison; Labelled; Graph; Data

Semistructured data is an important data format, essentially embodied by the XML standard. It is increasingly used in many critical applications, especially in business-to-business communications and peer-to-peer traffic on the Internet.The main advantage of the semistructured format is that it increases the flexibility of the way the data may be structured: as new situations arise, the structure of the data may evolve as well as the values.For example, given an established stream of business messages about car insurance between multiple brokers and underwriters, one underwriter may decide that the colour of a car is a significant factor not currently included in the data being supplied. They can advertise this fact, and brokers may choose to start asking their clients for the colour of their cars. From this point onwards, a field may start to appear in the messages between brokers and underwriters, the field being optionally included by brokers and optionally acted upon by underwriters where it is present.When much of this kind of activity takes place, it becomes important to consider the structural attributes of the whole, potentially large, pool of data, as well as the individual items. For example, given a set of data items: do they have anything much in common with each other?; do they all have at least something in common, and if so what?; how different is one given item from another, and are there any others exactly the same as this one?; can one or more clusters of similarly or identically-structured items be identified within the pool?; is the pool of data itself evolving or becoming quiescent, that is, over time, are individual items becoming, on the whole, more different or more similar?Recent work we have done on the inherent complexity, and thus regularity, of semistructured data items has led us to an observation that we believe will give great insights into how to answer these and other similar questions. Using some long-established results from Information Theory, we have applied the concept of mechanical entropy to the domain of semistructured data to give a metric for the complexity of individual data items. We have also discovered an efficient way of calculating this, by use of a data structure, the structural fingerprint, which represents the essential structure of the item. We now believe that the reapplication of this work into the above context will give a great leverage in terms of producing useful, quantified answers to the above questions and others, while the use of the structural fingerprint will make it computationally feasible to perform these calculations upon large pools of semistructured data in the global domain of the Internet.

半结构化数据是一种重要的数据格式，其本质体现为XML标准。它越来越多地用于许多关键应用程序，特别是在企业对企业的通信和互联网上的对等通信中。半结构化格式的主要优点是它增加了数据结构化方式的灵活性：随着新情况的出现，数据的结构以及值可能会演变，例如，给定在多个经纪人和承保人之间建立的关于汽车保险的商业消息流，一个承保人可以决定汽车的颜色是当前未包括在所提供的数据中的重要因素。他们可以宣传这一事实，经纪人可能会选择开始向客户询问他们汽车的颜色。从这一点开始，一个字段可能开始出现在经纪人和承销商之间的消息中，经纪人可以选择包含该字段，承销商也可以选择对其采取行动。当发生大量此类活动时，考虑整个数据池（可能很大）以及单个项目的结构属性变得非常重要。例如，给定一组数据项：它们之间有什么共同点吗？他们是否都至少有一些共同点，如果有的话，是什么？一个给定的项目与另一个有多大的不同，还有其他的项目与这个完全相同吗？是否可以在池中识别一个或多个相似或相同结构的项目集群？数据库本身是在演变还是在静止，也就是说，随着时间的推移，单个项目总体上是变得越来越不同还是越来越相似？最近的工作，我们所做的固有的复杂性，从而规律性，半结构化的数据项，使我们的观察，我们相信将提供很大的见解如何回答这些和其他类似的问题。使用信息论的一些长期建立的结果，我们已经将机械熵的概念应用于半结构化数据域，以给出单个数据项的复杂性的度量。我们还发现了一种有效的计算方法，通过使用数据结构，结构指纹，它代表了项目的基本结构。我们现在相信，将这项工作重新应用到上述背景下，将在产生有用的，量化的答案，上述问题和其他人方面提供很大的杠杆作用，而使用的结构指纹将使其计算上可行的执行这些计算上的大型池的半结构化数据在全球域的互联网。

项目成果

Similarity Search and Applications - 9th International Conference, SISAP 2016, Tokyo, Japan, October 24-26, 2016, Proceedings

相似性搜索和应用 - 第九届国际会议，SISAP 2016，日本东京，2016 年 10 月 24-26 日，会议记录

• DOI: 10.1007/978-3-319-46759-7_4
• 发表时间: 2016
• 作者: Connor R

A New Probabilistic Ranking Model

一种新的概率排名模型

• DOI: 10.1145/2499178.2499185
• 发表时间: 2013
• 作者: Connor R

Towards a universal information distance for structured data

迈向结构化数据的通用信息距离

• DOI: 10.1145/1995412.1995426
• 发表时间: 2011
• 作者: Connor R

Hilbert Exclusion Improved Metric Search through Finite Isometric Embeddings

希尔伯特排除通过有限等距嵌入改进了度量搜索

• DOI: 10.1145/3001583
• 发表时间: 2016
• 期刊: ACM Transactions on Information Systems
• 影响因子: 5.6
• 作者: Connor R