没有合适的资源?快使用搜索试试~ 我知道了~
--理论计算机科学电子笔记134(2005)33-53www.elsevier.com/locate/entcs基于欧拉图罗萨里奥·德基亚拉1ISISlab-Universit`adegliStudiiSalerno84081,Baronissi(萨莱诺),意大利Mikael Hammar2Apptus Technologies ABIDEON 研 究 中 心 SE-22370 Lund,Sweden维托里奥·斯卡拉诺1ISISlab-Universit`adegliStudiiSalerno84081,Baronissi(萨莱诺),意大利摘要在本文中,我们描述了如何使用欧拉图来表示虚拟目录。即,按需计算并满足多个约束的文件的集合。然后,我们简要描述了目前正在修改以包含此新功能的VENN FS项目的状态。特别是,我们展示了一个数据结构,旨在回答查询一个给定的欧拉图及其集。这里描述的数据结构EulerTree基于R树(参见[29]),这是一种设计用于回答二维空间中一系列形状的范围查询的关键词:欧拉图,文件系统,HFS,R树,EulerTree1 电邮地址:dechiara,dia.unisa.it2Email:Mikael.Hammar@a pp tus. C om1571-0661 © 2005 Elsevier B.V. 在C C BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.02.01934R. De Chiara等人/理论计算机科学电子笔记134(2005)331介绍文件访问和一般来说,文件管理是个人计算机日常使用中最常见的任务。文件访问和分类的方式受到文件系统本身设计的强烈影响。在设计文件系统时遵循的模式,即使是现代的文件系统,也是在层次结构中对信息进行分类的想法是直观的,即使是不喜欢计算机的人也很容易理解。自HFS的早期版本产生以来,其理论设计一直被日常生活隐喻所修饰,这极大地促进了它的差异:办公室隐喻。这个比喻简单地使用文件柜的概念来象征大容量存储,高级目录由抽屉表示,低级子目录可以表示为抽屉内的文件夹这个曾经鼓舞人心的比喻很快就过时了,并且有了局限性:“改进界面的方法不是开发对桌面越来越忠实的模仿,而是摆脱桌面的局限性。“. 这种模仿的一个典型例子是目录的定义(见[8]):这个比喻并非没有价值,因为正如[15]所述,&不幸的是,这个定义的一个重要遗产是强加在结构上的层次结构以及每个文件的“单一继承”:一个文件可以在一个地方一次,就像一张纸可以在一个文件夹中隐喻的使用帮助了80年代计算机的发展,当时个人计算甚至在最小的时间内进入。随着从命令行界面(CLI)向图形用户界面(GUI)的演变,图标隐喻已经被转移到指示文件夹、垃圾桶和通用文件的图标的图像中(见图1)。图标在颜色数量或分辨率方面不断发展,但其使用的语义从未改变。当HFS的想法出现时,CPU能力是一个严重的问题,因此,对文件的复杂操作,如管理元数据或复杂的目录结构,几乎是不可能的。在理解单一继承限制时需要考虑的另一个因素是,在70年代,管理的文件数量非常少。近年来海量存储可用空间R. De Chiara等人/理论计算机科学电子笔记134(2005)3335Fig. 1. GUI通过图标的演变:组(A)文件夹图标,组(B)文本文件图标,组(C)垃圾桶图标[19]这是一个非常复杂的问题,因为它的数量是按比例增加的。文件的结构在下一节中,我们将通过简要描述分层文件系统的结构和定义及其局限性来激励我们的工作。然后,我们提出并分析了“虚拟目录”的解决方案,我们提供了一个简短的文章,各种现有的系统。然后,我们介绍了我们正在开发的工具VENN FS和正在开发的一些考虑。VENN FS功能的目的是需要欧拉图的知识,以便正确创建目录结构。 因此,我们引入了一个数据结构,称为欧拉树,这是专为回答查询欧拉图。数据结构由R树(参见[29])导出,这是一种能够回答二维空间中形状族的范围查询2信息组织分层文件系统(HFS)结构[30]是文件系统的许多不同实现的启发性模式;它被广泛接受,很少被讨论[5]。这种等级结构之所以具有吸引力,有以下几个原因:• 易于理解:层次结构易于解释和理解。特别是在传统的办公场景中,HFS可以与现实世界的事物直接相关。这就是为什么所有的名字甚至在今天使用。• 可视化的多样性:有很多可视化36R. De Chiara等人/理论计算机科学电子笔记134(2005)33层次数据结构:二维节点-链路图[25]、水平家庭树图[26]和径向树图[27]。在过去的十年中,已经开发了新的可视化方法来显示大型层次结构,包括Treemap [25],圆锥树[17],圆盘树[23],双曲树[27]和3D双曲树[32]可视化。层次结构在现代操作系统中是如此普遍,存在一种称为“树视图”(见图2)的标准可视化控件• 层次导航层次结构的另一个好处是导航和找出用户在哪里的容易性。 考虑到传统上文件系统自发明以来的浏览方式,这一事实尤其如此:使用命令行界面(CLI)。在图2中显示了当前目录的众所周知的机制和命令cd的功能。cd命令(当前目录或者在某些实现中改变目录)和符号。(父目录)允许舒适地浏览层次结构,与cd.. 是可能的去一个级别和与cd目录名称是可能的去在目录目录名称的结构。为了跟踪位置,有一个特殊的变量在每个名为path的命令中更新:它以一种明确的方式说明了层次结构的哪一部分是当前目录。这种机制的最大优点是路径变量清楚地说明了两个可能的方向,即层次结构的向下和向上将把用户带到哪里。图二. cd(当前目录)命令,它允许浏览文件系统,给出用户当前所在的确切位置,路径。从命令行界面到图形用户界面(GUI)的演变只是提供了与cd命令相同的功能,但是在CLI中,用户可以仅处于层次结构的一个点,而在GUI中,通过使用多个窗口提供了多个访问点事实上,每个窗口都是文件系统的访问点,并在其上关联了一条路径,当然这可以加快许多文件管理任务,如图3所示。R. De Chiara等人/理论计算机科学电子笔记134(2005)3337图三.通过使用图形用户界面(GUI)进行的改进:可以在更当前的目录中同时访问文件系统。这大大有助于文件操作。自个人计算机出现以来,层次结构已经如此普遍,它们总是被认为是“组织事物的自然方式”,即使在与文件没有直接关系的情况下,例如我们的书签,我们的电子邮件,我们的使用层级作为对事物进行分类的独特方式的局限性在于,在快速发展的技术场景中,某些方面被故意忽略或没有充分利用。• CPU能力大幅提升。我们可以用计算机做更多的事情,比如更好、更高效的• 大容量存储器的大小和速度都有所增加。可用空间越多,用户记忆的文件就越多,这些文件也就越大,这通常意味着每个文件都与各种不同的主题相关。• 一般项目,所以不是“只是文件”,通常保存在我们的磁盘上,这些项目可以是非常丰富的信息,如音乐,例如,与一些表达相关的元数据,作者,流派,生产年份等。. .特别是音乐(例如.mp3文件)照片等。元数据是非常可靠的,因为它们是自动生成的。以层次结构组织信息已被广泛接受,甚至近年来设计的应用程序也使用类似硬盘上目录的层次结构这种趋势的一个明显例子是在我们的浏览器中组织互联网书签(例如Internet Explorer,Mozilla Firefox,Opera等)。)的。书签指的是网站,当然,充满了可以使用的信息。例如,这些信息可以用来以一种聪明的方式按主题重新组合书签,或者它们可以相互关联,或者可以自动分类。38R. De Chiara等人/理论计算机科学电子笔记134(2005)33但实际上在浏览器中实现的是书签的分层组织,因为它们是非表达性文件。层次结构的局限性是单一继承:一个项只能在树结构的一个叶子中。这一局限性在一篇论文[33]中也得到了明确的阐述,在该论文中,为了在日常工作中关注这些问题,进行了一项关于实际问题的研究。特别是明确强调,3虚拟目录如果限制是单继承来管理文件的多个性质,解决方案可以是多重继承。在最直观的意义上,多重继承与我们的PC当前管理的资源的性质事实上,我们的硬盘上可用的空间越多,可用的文件就越多,文件的复杂性和数据的异质性就越大3.1符号链接需要简要考虑一下文件系统所使用的符号链接,以使文件“出现”在分层目录结构中的两个或多个位置。符号链接是一个特殊的文件,它的行为类似于指针,当一个命令在符号链接上执行时,真正发生的是这个命令在它所指向的文件上执行。符号链接非常强大,它们甚至可以使远程资源看起来像是本地的。使用符号链接的缺点是,它们容易出现一些不一致的地方,比如当指向的文件被删除或移动时。对于单个文件的情况,符号链接可能是合适的,甚至是优雅的。3.2定义虚拟目录(VD)是一个目录,可以以通常的方式访问,但它是按需计算回答一个查询。从虚拟目录与搜索工具不同,搜索工具查找与用户提供的规则匹配的文件,而虚拟目录不断检索文件并通过传统的目录界面提供R. De Chiara等人/理论计算机科学电子笔记134(2005)3339作为按需组装的虚拟目录,一个文件在一个虚拟目录中的存在并不意味着这个文件不会出现在其他虚拟目录中:单一继承的解决方案。当然,虚拟目录的计算通常忽略了文件保存的先前存在的层次结构,传统的文件系统变得复杂。3.3实施方式各种制造商都认为需要一个系统的、集成良好的单一继承解决方案,它们打算为用户提供系统范围的解决方案,以不同的方式对文件进行分类,而不是层次结构。我们在这里提供了一个小的分析各种技术将在这些年来提出。语义文件系统。 在[28]中描述了“语义文件系统”其中文件保存在传统的文件系统中,但使用虚拟目录机制访问。该文件中所描述的系统中管理的文件是来自USENET档案的新闻,这些新闻非常变了 在[14]中提出的系统中,每个资源都与之相连用户定义属性的可变数量。 虚拟目录也是根据用户查询的需要创建的。Presto使用一个数据库来保存有关管理文件的信息。Presto系统允许用户定义文件的任何属性名称,为这种分类提供了极大的灵活性Presto中的一些有趣之处在于:(a)属性保存在数据库中,(b)Presto通过NFS(网络文件系统)接口提供对资源的访问,从而实现与现有应用程序的强大兼容性。WinFS。尚未到来的MicrosoftWinFS(Windows Future Storage)是代号为Longhorn的新操作系统的支柱之一。WinFS([9])将提供一个强大的全边缘数据库,作为正在进行的可扩展文件系统。在WinFS中,文件系统也是通过组装虚拟目录来访问的。像“我的音乐”和“我的图片”这样广泛存在的传统目录WinFS不使用HFS来组织信息,而是使用直接非循环项图(DAG)。它是一组存储的项及其关系,其物理存储是一个关系数据库,支持存储任何项层次结构。在开发人员的意图中,通过这种新颖的存储方法,WinFS将提供文件系统中以前从未梦想过的搜索能力。可以根据其属性的价值找到物品,甚至可以40R. De Chiara等人/理论计算机科学电子笔记134(2005)33与它们相关的项目的属性值开发人员面临的一个问题是计算成本 运行一个完整的边缘数据库,称为育空地区,提供所需的关系功能。在[33]中再次断言自动分类将如何极大地改进工作,以一些用户的努力为代价3.4搜索工具还有另一类与文件系统结构相关的工具,实际上认为它是绝对非结构化的。这些工具具有嵌入在通常的操作系统用户界面中的某个地方的小工具的一般外观。见图4。搜索框嵌入在操作系统。它们对几乎所有文件进行分类,允许系统范围内的搜索。(a)存储,(b)苹果:聚光灯(c)Longhorn:搜索框(d)谷歌桌面存储([2])旨在用一种新的文档存储来取代传统的文件系统,在这种存储中,文档保持非结构化,并且通过自然语言查询来提供检索。搜索结果可以保存在虚拟目录中,与现有的传统文件系统和应用程序向后兼容Spotlight ( [7]) 是一 个嵌 入在 Mac OS X Tiger 版 本中 的搜 索工 具。Spotlight决定只对某些类型的文档和媒体进行分类。Spotlight的工作原理类似于搜索框,它提供按媒体分类的搜索结果(见图4)。(b))。这种方法也与Microsoft Windows中的常见搜索框相匹配(见图4)。(c)Longhorn版本)。Spotlight还允许将搜索结果保存在虚拟目录中。R. De Chiara等人/理论计算机科学电子笔记134(2005)3341Google Desktop([3])是Google提供的一种工具,用于扩展知名在线搜索引擎的搜索结果,并将结果显示在用户的硬盘上。GoogleDesktop会持续扫描硬盘,以找到它可以处理的某些文件,主要是文本文件,如.doc,. pdf。、.html等。. .一些特别的解决方案也被提议用于分隔的上下文,如电子邮件客户端:Ximian Evolution[1]有很好的效果。Ximian Evolution vFolder看起来像一个文件夹,但没有物理连接到它的邮件。相反,vFolder由一组标准定义,就像邮件搜索一样。不必每次都手动输入搜索条件:vFolder始终包含所有符合其条件的物理邮件文件夹中的最新邮件。蝙蝠侠![6]也有虚拟文件夹,自动收集所有符合细粒度标准的电子邮件,这些标准以通常的虚拟目录方式工作。4虚拟目录我们在这里介绍的应用程序是一个可以在日常活动中帮助用户的工具。我们的工作遵循了开发VENN FS[11]的研究路线,该研究路线允许用户将文档和类别放置在一个平面上,其中文件可以同时属于多个类别,通过使用众所周知的直观欧拉图来图形化地表示每个类别。我们特别注意设计一个界面,虽然完全可视化,但只要求用户进行很少和快速的交互。4.1VENN FS主要特点我们在这里提供了一个简短的调查,目前版本的VENN FS提出了一个几乎无限的表面上,用户可以自由地绘制矩形表示一个集。矩形可以以非常直观的方式绘制,第一次点击放置周围矩形的第一个角,然后通过移动鼠标可以自由变形形状。这种简单的机制允许用户弄清楚将要创建的内容。创建新集合的有趣之处在于,在变形形状的同时,整个图也会更新,因为允许用户弄清楚哪些是新创建的交点是很重要的。在[22]中也可以找到一种类似的绘制类别的机制,其中放置元素,其中描述了一种用于自动对媒体进行分类的工具。42R. De Chiara等人/理论计算机科学电子笔记134(2005)33在平面上表示文件有几个优点[31],因为我们通过平面上的接近度来表示主题的接近度(类别之间以及文档之间),从而推动用户将数据关系设置为空间关系。暗示用户将相关的类别彼此靠近,因为它允许它们部分重叠,而完全不相关的类别直观地放置在远处。使用距离来关联文档的一个有趣的视觉结果是,通过缩放区域并放大/缩小以达到所需的级别,可以隐式地获得主题过滤。我们的目标是为用户提供一种工具,使其能够轻松绘制由他/她自己的文档(非结构化)语料库表示的环境,将文档放入(可能是多个)类别并通过接近度将类别关联起来:通过构建该环境的认知地图[34由于环境是由用户自己创建的,因此(使用我们的工具创建的)物理布局在人类头脑中的内在类比变得更容易掌握。从某种意义上说,人们可以将VENN FS视为一种使其文档的认知地图明确且易于导航的方式。为了方便导航,我们提供了放置地标的功能,因为众所周知,它们的识别有助于导航[13]以及学习和记忆[24]。地标与文件不对应它们的列表显示给用户,每个人都可以很容易地通过双击地标的标签。地标的使用也在[31]中进行了研究。通过使用一个容易理解的比喻来表明文件的最近程度:最近(即最近访问的)文件是然后,重要的是允许在时间上进行过滤(通过使用滑块),以便仅显示最后修改日期低于给定日期的文件。4.2VENN FS中的虚拟目录VENN FS旨在有效地将用户头脑中的结构传达到文件集合中,以便可以存储,检索和更新。所有自动化工具都面临着一个隐含的限制:不同文件之间的联系通常只对人类可用(即欧拉图非常直观,R. De Chiara等人/理论计算机科学电子笔记134(2005)3343图五.当前版本的VENN FS的屏幕截图。这些类别还使用省略号可视化。对于非专业用户的使用是有用的(参见,例如,欧拉图如何用于表示[10]中复杂查询的结果虚拟目录的持久性使其成为一种通用工具,因为可以(手动)添加其他项目。此外,查询被持续监控,因此可以添加虚拟目录中存在的文件中发生的更改(例如新条目)。仔细调整监视的数据大小以及监视的频率对于保持应用程序的效率非常重要(参见图6)。当发现新的项目时,当然必须通知用户,并且资源被放置在平面中的一通过拖放,用户可以将项目放置在正确的位置,以及创建新的类别。显示不再属于查询结果的项目(移动或删除)(对于短时间段)从图中慢慢消失,以便通知用户发生了变化。另一个令人兴奋的愿景是,我们可以重复使用查询的虚拟目录,其结果是虚拟目录以及。这意味着用户有机会将几个虚拟目录连接在一起,这些虚拟目录表示对同一材料的不同尺寸进行过滤4.3呈现给用户当前的图形板具有更高的能力,可以创建惊人的图形效果,这些效果曾经被降级到专用软件(娱乐,CAD)中,现在可以在我们日常的个人电脑上使用(免费)。趋势是利用这种硬件来大大提高吸引力,外观和功能-44R. De Chiara等人/理论计算机科学电子笔记134(2005)33见图6。 从查询创建虚拟目录的示例。传统的工具,如文件浏览器。这一普遍趋势也在[9]中得到了注意。在VENN FS中,我们利用了这些功能(alpha混合,缩放,相机效果、平滑过渡等。.使得所提供的界面对用户来说更加动态和支持。作为一个例子,我们可以引用此外,“类别选择”是可视化的,通过使用一个平滑的动画(由图形板提供)。利用图形硬件还可以解决经典的几何问题,例如,它可以用来快速回答诸如“多边形中有一个点”之类的查询在当前的VENN FS开发中,我们的目标是三个主要目标,如[33]所述:• 创建分类:这项任务是使用用户手工绘制的欧拉图的直观性来完成的。集合可以是主题、主题、目录等。.以及我们生活中所有可能涉及到的各个方面,而且这个概念非常容易理解,即使是新手用户也不需要解释。• 分类信息:这是使用用户非常熟悉的众所周知的“拖放”机制来执行的。将文件拖动到一个点在VENN FS的平面上,直观地将文件“放入”在该点重叠的集合中。重叠的集合被渲染为混合它们的颜色。有一个令人兴奋的观点,我们仍在调查,并将其与ev. 每个类别是一组属性,由集合中的元素继承。这是其他人已经跨越的诱人方式([9],[14]),其中文档和文件被处理为数据库中的行。 我们还打算 为了向在目录图标上执行的拖放操作提供重要性R. De Chiara等人/理论计算机科学电子笔记134(2005)3345将立即创建一个以该目录命名的新集合。在一些早期的用户测试中,我们得到了提供一种“向导”的建议,这将是使用VENN FS的一个很好的起点。• 检索信息:这是一个有趣的功能,它涉及布尔表达式解析器的实现,以在图上执行具有挑战性的部分是可视化查询结果,而不是以文本方式提供它们。目前在这个方向的工作打算再次利用OpenGL提供的平滑缩放操作:这个想法是缩小图表阴影到灰色色调,让结果闪烁。结果如图7所示。一旦可视化,可以将查询拖到HFS上的某个位置,以创建虚拟目录。见图7。 查询结果可视化: 红色和浅蓝色的元素会缩小以显示整个结果,淡出设置颜色以更好地显示所选元素的闪烁。5欧拉图在本节中,我们定义了一个名为EulerTree的数据结构,它将被VENN FS使用,以便有效地回答关于欧拉图的查询。该数据结构源自R树(参见[29]),这是一种能够支持二维空间中形状族的范围查询的数据结构。5.1定义我们的目标是管理类别(集合)。将考虑二维空间集合是定义良好的形状(没有徒手集合)。特别是,我们限制我们的注意矩形集。这不是一个真正的限制,46R. De Chiara等人/理论计算机科学电子笔记134(2005)33--如图所示[16]。我们认为集合和矩形是可互换的术语.当然,集合可以在空间中的任何地方,适当地相互交叉或一个在另一个里面。我们在这里提供一些非正式的定义:空间:我们将参考二维空间。实际上,所提出的数据结构可以扩展到其他更高维的空间,但由于我们的研究计划用于实验场景,我们将不会进一步研究。集合或矩形:在本文中,我们将集合定义为矩形轴对齐的矩形(isotheticrectangles)。图:让图表示一个集合C = C1,C2,.,Cn的任意集合。“自由放置”意味着集合可以是不相交的,重叠的或在另一个里面。空间中的每个点都可以在int(Ci)(Ci的内部)或ext(Ci)(Ci的外部)中。 每个集合的边界都在int(Ci)中。子面:子面是由一个或多个集合所包含的平面区域。图9中的(a)子面变灰。子矩形:矩形子面称为子矩形。次矩形是由图的重叠集生成的。在图10中,我们展示了SweepLine算法(见5.4节)的结果,该算法将子面切割成一个或多个子矩形。见图8。 EulerTree数据结构的一般方面。EulerTree基于R-Tree数据结构,因此它实现了R-Tree数据结构提供的所有查询。R-树用于各种几何环境。使用更支持的数据结构的想法是基于一些图表设计提示的需要,实际上将使用这种数据结构的应用程序是VENN FS(参见[11],[12])在VENN FS中,我们还感兴趣的是一种方法,以获得图信息,灰指的是一个以上的集合。R. De Chiara等人/理论计算机科学电子笔记134(2005)3347√5.2R树描述R树(最初由[20]引入)旨在回答范围查询(窗口查询):给定Rd中的对象集合,范围查询报告与d维轴对齐查询窗口(即d维框)相交的所有对象。我们将参考二维空间,所以d将为2,对象将是等距矩形。R树是一种特殊的B树,其中每个叶子都保持一个输入框。更多的细节可以在[29]中找到。给定S是R2中n个可能相交的盒子的集合,S的完美平衡盒子树可以在O(nlogn)时间内构建。 一个范围查询可以在O(n+klogn)内回答,返回k个矩形(在二维空间中)。5.3EulerTree数据结构我们提出了一个初步的数据结构,似乎是适合有效地表示欧拉图的分析。EulerTree是R树的扩展,旨在追溯图中相交集创建的子面。图8. (a)描述了R树是如何扩展的:在树下添加了一个称为Set Nodes的节点级别,它将为图中的每个集合保留一个节点。R树叶子和集合节点之间的链接称为接口:当且仅当子面属于集合时,在集合节点和R树的子面叶子之间的接口中创建链接。数据结构EulerTree旨在用于检索有关动态变化的图的信息。EulerTree必须回答的查询是:• 什么是集合A的真子集?• 哪些集合与集合A相交?该图将一次绘制一组。一旦插入,一个集合将可能与其他集合重叠,生成一个或多个与相关子面的相交此修改将立即反映在EulerTree上。图9. (a)显示了由两个相交的集合组成的欧拉图:子矩形s1,s2和s4被创建为分裂子面灰色。图9. (b)EulerTree相对于图。在图中插入一个新的集合是使用R-Tree提供的查询和删除操作来执行的,分为两个阶段:(i) 在第一阶段,我们查询R树,以检查哪些是插入新集合所涉及的子面。48R. De Chiara等人/理论计算机科学电子笔记134(2005)33←←见图9。(a)一个欧拉图和相关的欧拉树(b),灰色的子面。 在(c)接口的细节以及如何管理交叉点。 特别是子矩形s3属于并且这种情况被边缘正确地报告。(ii) 在第二阶段,这些矩形从R树中删除,处理并重新插入R树中。为了更好地解释细节,我们简要描述一下什么是R树。EulerTree由使用算法Sweepline的算法1更新下一小节中描述的拆分。算法1在数据结构中插入一个新的矩形Input:R要插入T的新矩形,EulerTree。输出:更新T1:将Set Node R添加到EulerTree。第二章:s:Query(T,R). 3:从T的R树中删除s。第四章: z:<ρ1,.,ρm>SweeplineSplit(R,s).5:在T中插入z,将每个s i连接到右Set。让R表示我们想插入到欧拉树中的矩形(集合)。首先,我们将其添加到树结构中,并在EulerTree中进行查询以获得与R相交的所有子矩形。这些子矩形将从R树中删除。接下来,我们运行SweeplineSplit算法来计算新的子矩形集.结果细分中的每个子矩形面都包含指向其所属集节点的指针。因此,将这些面添加到R-R. De Chiara等人/理论计算机科学电子笔记134(2005)3349树更新EulerTree。请注意,R树中的每个矩形都被假设为保留一个属性,该属性是它所属的所有集合节点的指针列表5.4Sweepline分裂算法为了计算通过在图中插入一个新矩形而获得的平面细分,我们使用一种众所周知的技术,称为地图覆盖。矩形由双连接边列表表示。该数据结构表示平面细分,并且由一组顶点、一组半边和面组成,所有这些都根据它们在平面细分中的相邻性连接。半边是表示线段的一侧的有向边。因此,线段由两个方向相反的半边表示矩形细分的双连接边列表有一个无界面,它不属于任何Set Nodes。这个面本身不需要是矩形。所有其他面必须是矩形,它们表示子矩形,子矩形又构成“设置节点”的交点。因此,每个这样的面都有一个指针列表,用于跟踪它所属的集合节点。当我们插入一个新矩形时,子矩形的集合需要在操作后保持不相交。因此,有必要将查询矩形和查询矩形分割成新的子矩形。这是使用sweepline技术完成的。分裂算法的输入是两个subdivisions代表查询矩形和矩形相交输出是一组新的不相交子矩形。该算法分两个阶段工作。在第一阶段,我们计算两个细分的叠加。两个细分S1和S2的重叠被定义为由S1和S2的边引起的平面细分。覆盖中的每个面都保持指向包含它的S1和S2中的面的指针。因此,在计算覆盖之后,更新覆盖中每个面的设置节点指针列表使用[21]第2.3章中的MapOverlay算法计算叠加。该算法的时间复杂度为O(klogk+kjlogk),其中k是与查询矩形相交的矩形个数,KJ是覆盖图中的面个数。覆盖包含非矩形的面。这些必须进一步划分。我们使用一个简单的sweepline算法来找到这样的分区。它的工作原理如下:sweepline从左到右。在任何时候,我们都要求扫描线左边的垂直半直线都不能界定有界面,并且没有一个反射顶点作为原点或终点。如果没有边界50R. De Chiara等人/理论计算机科学电子笔记134(2005)33⟨⟩面包含rexex顶点,它们都是凸的,在我们的情况下,这意味着它们是矩形的。如果我们找到一个顶点,我们添加一个垂直边,即,一对半边,添加到边列表中,使顶点不重复。所有更新都包含在MapOverlay算法中完成的更新的子集。见图10。 一个应用SweepLine算法的例子。我们注意到添加垂直边会将面分为两部分。但是,面属性保持不变,因为新矩形属于相同的“设置节点”。时间复杂度为O(kJlogkJ)。5.5删除集合为了从EulerTree中删除给定的集合,我们提供算法2。算法2从数据结构中删除一个集合输入:T是EulerTree,S是要从T中删除的集合。输出:更新T1:对于S上的所有子空间r,2:如果出度(r)== 1,则3:从T的R树中移除r4:去除边缘 r,S 从接口5:如果结束第六章: 端7:从EulerTreeT中删除S集合S的删除是通过简单地从R树中删除S的所有不与图中的其他集合共享的子空间来执行的。对于一个给定的子矩形,这个条件在for.算法2中的循环,只是检查出度正好是1,这意味着子矩形由集合S定义。图11给出了一个示例。删除算法的一个严重缺点是存在一些不必要的子矩形(例如,参见图11中的s1,s2,s3,s4),这些子矩形可以合并到更大的矩形中6结论和今后的工作我们使用VENN FS的经验为我们提供了来自用户的良好反馈,但当然这不是一个严肃的可用性测试,每个工具都可以使用它。R. De Chiara等人/理论计算机科学电子笔记134(2005)3351见图11。一个示例显示了应用于Set2的删除操作。操作的结果显示在图中以及EulerTree的界面中。图和欧拉树的接口。在(a)中,在算法2的for循环中检查的集合2和两个子矩形s3和s5是灰色的。 (b)显示了删除Set2的结果,仅删除子矩形s5实 际 上 被删除了,而子矩形s3被保留了, 因为它与Set 1共享。必须提交给。我们打算执行的另一个步骤是使用欧拉图来组织其他上下文中的信息,例如书签和电子邮件。管理电子邮件和书签将不同于管理通用文件,因为,例如,存在比较两封电子邮件的简单方法(例如,主题中的单词,收件人地址等)。. . ),这些比较方法可用于自动将元素放置在集合中。一个具有挑战性的目标是设计一个紧凑的表示,一个可以与众所周知的分层表示相竞争的图表。对于层次结构,正如我们所说的,有很多不同的和有效的可视化技术,但对于日常工作,最广泛和有效的是树视图(如图2所示)。为了在常用应用中显示欧拉图,需要一种紧凑、易于解释的表示法,如在结论上,一些批评者可能会出现的内在限制的表现力,因为使用isothetic矩形:例如,在一个4集图可能是不可能的,以提供某些交叉或错误的交叉,可以推断(见[4])。使用更复杂的数字(例如k-blob和blob)可以绕过这些限制。由于我们的研究强烈面向应用,我们更喜欢管理(例如绘制,拉伸,移动)矩形集的可用性,而不是使用更复杂的图形设计的图表的潜在表现力。52R. De Chiara等人/理论计算机科学电子笔记134(2005)33引用[1] 进化.网址http://gnome.org/projects/evolution[2] 侏儒存储. 网址http://www.gnome.org/~seth/storage/features.html[3] Google Desktop . 网址http://desktop.google.com/[4] 图解表示和推理的局限性。URLhttp://plato.stanford.edu/entries/diagrams/#3.1[5] 命名系统冒险。网址http://namesys.com/whitepaper.html[6] Ritlabs:蝙蝠。 网址http://www.ritlabs.com/en/[7] 聚光灯技术 . 网址http://www.apple.com/macosx/tiger/spotlight.html[8] 维基百科:目录 . 网址http://en.wikipedia.org/wiki/Directory[9] WinFS. 网址http://msdn.microsoft.com/Longhorn[10] Blackwell,A. F.、K. Marriott和A. Shimojima,editors,[11] De Chiara河,联合Erra和V. Scarano,VennFS:一个维恩图文件管理器,在:第七届信息可视化国际会议论文集,IV 2003,2003年7月16-18日,伦敦,英国,2003年。[12] 德·基亚拉 R., 联合 Erra 和V. Scarano, 一 视觉自适应 接口 到 文件 系统,在:2004年高级视觉界面工作会议论文集,第10页。366-369[13] Dillon,A.,J. Richardson和C. McKnight,超文本中的导航:对概念的批判性评论,载于:Diaper,D.,Gilmore,D.,Cockton,G.,Shackel,B. (Eds)03 The Dog(1990)[14] Dourish , P. , K. W. 爱 德 华 兹 , A. LaMarca 和 M. Salisbury , Presto : An ExperimentalArchitecture for Cumulid Interactive Document Spaces , ACM Transactions on Computer-Human Interaction(1999),pp. 133-161。[15] Fertig,S.,E. Freeman和D. Gelernter,发现和提醒重新考虑,SIGCHI公牛。28(1996),pp. 六十六比六十九[16] Flower,J.,P. Rodgers和P. Mutton,用于eXtreme图的布局度量,在:第七届信息可视化国际会议(IV03)(2003),pp.272-280。[17] G. G. Robertson和J.D. Mackinlay和S. K. Card,Cone Trees:Animated 3D Visualizations ofHierarchical Information,in:Proc. of CHI-91,New Orleans,LA,1991,pp. 189-194.[18] Gentner,D. J. Nielsen,网址http://www.acm.org/pubs/cacm/AUG96/antimac.htm[19] Grochowski E., H. R., 硬盘驱动器的未来趋势,IEEE磁性Vol.32,Iss.3(1996),pp. 1850年至1854年。[20] Guttman,A.,R-trees:a dynamic index structure for spatial searching,in:Proceedings ofthe 1984 ACM SIGMOD international conference on Management of data,1984,pp.四十七比五十七[21] Hammar,M.,M. de Berg,J. Gudmundsson和M. H. Overmars,关于低刺数的r-树,在:欧洲算法研讨会,2000年,pp.167-178.URLciteseer.ist.psu.edu/313683.html[22] Hyunmo Kang和Ben Shneiderman,MediaMonitoring:一个具有语义区域的动态个人媒体管理接口,载于:CHI764-765。
下载后可阅读完整内容,剩余1页未读,立即下载
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 基于Springboot的医院信管系统
- 基于Springboot的冬奥会科普平台
- 基于Springboot的社区医院管理服务系统
- 基于Springboot的实习管理系统
- TI-TCAN1146.pdf
- 基于Springboot的留守儿童爱心网站
- S32K3XXRM.pdf
- Ansible Automation Platform 快速安装指南 v3.8.1
- Ansible Tower 发行注记 v3.8.1-76页
- C语言笔记-考研版(进阶)
- Design_of_Analog_CMOS_Integrated_Circuit20200602-85440-9wt61m-with-cover-page-v2 (1).pdf
- Ansible Automation Platform 安装和参考指南 v3.8.1-59页
- 浅析5G技术在工业互联网领域的应用研究
- 查重17 岑彩谊-基于otn技术的本地承载网-二稿 .docx
- 自考计算机应用基础知识点.doc
- 数据库系统安全、技术操作规程.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)