-
公开(公告)号：US09135565B1
公开(公告)日：2015-09-15
申请号：US13451894
申请日：2012-04-20
申请人： Mohamed Elbassiony Mohamed Abou El Alaa Khalefa , Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski , Grzegorz Malewicz
发明人： Mohamed Elbassiony Mohamed Abou El Alaa Khalefa , Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski , Grzegorz Malewicz
IPC分类号： G06F15/17 , G06N99/00 , G06F15/173
CPC分类号： G06T11/206 , G06F7/00 , G06F8/457 , G06F9/46 , G06F9/5005 , G06F11/1464 , G06F11/1469 , G06F11/2082 , G06F15/17312 , G06F17/30 , G06F17/30958 , G06F17/30961 , G06F2201/84 , G06F2221/0793 , G06N99/00 , G06N99/005 , G06T2210/32 , H04L5/0032 , H04L29/08135 , H04L67/10
摘要： Data are maintained in a distributed computing system that describe a directed graph representing relationships among items. The directed graph has a plurality of vertices representing the items and has edges with values representing distances between the items connected by the vertices. A multiple reference point algorithm is executed for a plurality of the vertices in the directed graph in parallel for a series of synchronized iterations to determine shortest distances between the vertices and the source vertex. After executing the algorithm on the vertices, value pairs associated with the vertices are aggregated. The aggregated value pairs indicate shortest distances from the respective vertices to the source vertex. The aggregated value pairs are outputted.
摘要翻译： 在分布式计算系统中维护数据，该分布式计算系统描述表示项目之间的关系的有向图。 有向图具有表示项目的多个顶点，并且具有表示由顶点连接的项目之间的距离的值的边。 针对一系列同步迭代并行地对有向图中的多个顶点执行多参考点算法，以确定顶点与源顶点之间的最短距离。 在对顶点执行算法之后，聚合与顶点相关联的值对。 聚合值对表示从各个顶点到源顶点的最短距离。 输出聚合值对。
-
公开(公告)号：US08645429B1
公开(公告)日：2014-02-04
申请号：US13432806
申请日：2012-03-28
申请人： Aart J. C. Bik , Matthew H. Austern , James C. Dehnert , Grzegorz Czajkowski , Grzegorz Malewicz , Naty Leiser
发明人： Aart J. C. Bik , Matthew H. Austern , James C. Dehnert , Grzegorz Czajkowski , Grzegorz Malewicz , Naty Leiser
CPC分类号： G06T11/206 , G06F7/00 , G06F8/457 , G06F9/46 , G06F9/5005 , G06F11/1464 , G06F11/1469 , G06F11/2082 , G06F15/17312 , G06F17/30 , G06F17/30958 , G06F17/30961 , G06F2201/84 , G06F2221/0793 , G06N99/00 , G06N99/005 , G06T2210/32 , H04L5/0032 , H04L29/08135 , H04L67/10
摘要： Resolving conflicting graph mutations in a distributed computing system. Graph data for at least a partition of a graph is stored in a worker system of a distributed computing system. The graph represents relationships among a set of tangible items that model a real-world condition having an associated problem. A plurality of conflicting mutation requests are received to mutate the graph. A conflict between the mutation requests is resolved with a conflict resolution function that lacks direct access to the graph data. The graph data is updated responsive to a result generated by resolving the conflict using the conflict resolution function.
摘要翻译： 解决分布式计算系统中的冲突图突变。 至少图形分区的图形数据存储在分布式计算系统的工作系统中。 该图表示对具有相关问题的真实世界条件建模的一组有形项目之间的关系。 接收多个冲突变异请求以使图形变异。 突变请求之间的冲突由解决冲突的功能解决，缺少对图形数据的直接访问。 响应于通过使用冲突解决功能解决冲突而产生的结果来更新图形数据。
-
公开(公告)号：US09385845B1
公开(公告)日：2016-07-05
申请号：US13449249
申请日：2012-04-17
申请人： Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski , Grzegorz Malewicz
发明人： Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski , Grzegorz Malewicz
CPC分类号： G06T11/206 , G06F7/00 , G06F8/457 , G06F9/46 , G06F9/5005 , G06F11/1464 , G06F11/1469 , G06F11/2082 , G06F15/17312 , G06F17/30 , G06F17/30958 , G06F17/30961 , G06F2201/84 , G06F2221/0793 , G06N99/00 , G06N99/005 , G06T2210/32 , H04L5/0032 , H04L29/08135 , H04L67/10
摘要： A value is distributed in a distributed computing system having a master system in communication with a plurality of worker systems. Partitions of a graph are assigned to the worker systems. The graph represents relationships among a set of tangible items that model a real-world condition having an associated problem. Configuration information is determined that describes a configuration of the distributed computing system. A distribution scheme is selected for distributing a value from the master system to the plurality of worker systems based on the configuration information. The value is distributed from the master system to the worker systems according to the selected distribution scheme. The worker systems are configured to use the value to produce an output representing a solution to the real-world problem.
摘要翻译： 值分布在具有与多个工作者系统通信的主系统的分布式计算系统中。 图形的分区分配给工作系统。 该图表示对具有相关问题的真实世界条件建模的一组有形项目之间的关系。 确定描述分布式计算系统的配置的配置信息。 选择分配方案，用于基于配置信息将值从主系统分配给多个工作者系统。 该值根据选定的分配方案从主系统分配给工作系统。 工作者系统被配置为使用该值来产生表示对现实世界问题的解决方案的输出。
-
公开(公告)号：US09026850B1
公开(公告)日：2015-05-05
申请号：US13451450
申请日：2012-04-19
申请人： Grzegorz Malewicz , Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski
发明人： Grzegorz Malewicz , Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski
CPC分类号： G06T11/206 , G06F7/00 , G06F8/457 , G06F9/46 , G06F9/5005 , G06F11/1464 , G06F11/1469 , G06F11/2082 , G06F15/17312 , G06F17/30 , G06F17/30958 , G06F17/30961 , G06F2201/84 , G06F2221/0793 , G06N99/00 , G06N99/005 , G06T2210/32 , H04L5/0032 , H04L29/08135 , H04L67/10
摘要： Executing a confined recovery in a distributed system having a plurality of worker systems including a failed worker system at a current superstep. The confined recovery includes determining states of the partitions of the worker systems during the supersteps preceding the current superstep, and determining a recovery initiation superstep preceding the current superstep in which all messages for recovery initiation superstep are available. The recovery initiation superstep is determined responsive to determining the states of the partitions. Additionally, a recovery set of partitions is determined for which messages in supersteps after the recovery initiation superstep are not available. The worker systems having the partitions in the recovery set are instructed to execute the defined function for the partitions in the recovery set starting at the recovery initiation superstep to recover the lost exchanged messages.
摘要翻译： 在具有多个工作系统的分布式系统中执行限制恢复，包括当前超级步骤中的故障工作系统。 限制恢复包括在当前超级步骤之前的超级步骤中确定工作者系统的分区的状态，以及确定在当前超级步骤之前的恢复启动超级步骤，其中用于恢复启动超级步骤的所有消息都可用。 响应于确定分区的状态来确定恢复启动超级步骤。 另外，确定在恢复启动超级步骤之后的超级步骤中哪些消息不可用的恢复分区集合。 指示具有恢复组中的分区的工作系统对在恢复启动超级步骤开始的恢复集中的分区执行定义的功能，以恢复丢失的交换的消息。
-
公开(公告)号：US09495477B1
公开(公告)日：2016-11-15
申请号：US13353556
申请日：2012-01-19
申请人： James C. Dehnert , Matthew H. Austern , Aart J. C. Bik , Grzegorz Czajkowski , Grzegorz Malewicz , Ilan Horn , Naty Leiser
发明人： James C. Dehnert , Matthew H. Austern , Aart J. C. Bik , Grzegorz Czajkowski , Grzegorz Malewicz , Ilan Horn , Naty Leiser
CPC分类号： G06T11/206 , G06F7/00 , G06F8/457 , G06F9/46 , G06F9/5005 , G06F11/1464 , G06F11/1469 , G06F11/2082 , G06F15/17312 , G06F17/30 , G06F17/30958 , G06F17/30961 , G06F2201/84 , G06F2221/0793 , G06N99/00 , G06N99/005 , G06T2210/32 , H04L5/0032 , H04L29/08135 , H04L67/10
摘要： Data are maintained in a distributed computing system that describe a directed graph representing relationships among a set of items. The directed graph models a condition having an associated problem. The directed graph has graph components having associated data fields. The relationships are analyzed to identify a solution to the problem. As part of the analysis, a new value for the data field associated with a graph component is identified responsive to an operation performed during the analysis. The new value is compared with an existing value of the data field, and the data field is modified. The modification may include inserting the new value into an overflow vector of data, and replacing the existing value in the data field with exception information identifying the location of the new value. An exception flag associated with the data field is set to indicate that the exception information is being used.
摘要翻译： 在分布式计算系统中维护数据，该分布式计算系统描述表示一组项目之间的关系的有向图。 有向图模型具有相关问题的条件。 有向图具有具有相关数据字段的图形分量。 分析关系以确定问题的解决方案。 作为分析的一部分，响应于在分析期间执行的操作，识别与图形组件相关联的数据字段的新值。 将新值与数据字段的现有值进行比较，并修改数据字段。 修改可以包括将新值插入到数据的溢出向量中，并且用标识新值的位置的异常信息替换数据字段中的现有值。 与数据字段相关联的异常标志被设置为指示正在使用异常信息。
-
公开(公告)号：US08880941B1
公开(公告)日：2014-11-04
申请号：US13452299
申请日：2012-04-20
申请人： Charles Reiss , Grzegorz Malewicz , Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski
发明人： Charles Reiss , Grzegorz Malewicz , Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski
IPC分类号： G06F11/00
CPC分类号： G06T11/206 , G06F7/00 , G06F8/457 , G06F9/46 , G06F9/5005 , G06F11/1464 , G06F11/1469 , G06F11/2082 , G06F15/17312 , G06F17/30 , G06F17/30958 , G06F17/30961 , G06F2201/84 , G06F2221/0793 , G06N99/00 , G06N99/005 , G06T2210/32 , H04L5/0032 , H04L29/08135 , H04L67/10
摘要： Instructing a plurality of worker systems in a distributed computing system to perform a checkpoint. Instructing the worker systems includes receiving timing messages from the plurality of worker systems and determining, based on the received timing messages, a common checkpoint time indicating an estimated amount of time to be taken by the plurality of worker systems to write data to the persistent storage for a subsequent checkpoint. The common checkpoint time is used to determine a checkpoint threshold, and responsive to the determined checkpoint threshold, it is determined whether to perform the checkpoint. Responsive to determining to perform the checkpoint, messages are transmitted to the plurality of worker systems instructing the worker systems to perform the checkpoint.
摘要翻译： 指示分布式计算系统中的多个工作系统执行检查点。 指示工作者系统包括接收来自多个工作者系统的定时消息，并且基于接收到的定时消息来确定指示多个工作者系统将持续存储器写入数据所估计的时间量的公共检查点时间 用于后续检查点。 公共检查点时间用于确定检查点阈值，并且响应于确定的检查点阈值，确定是否执行检查点。 响应于确定执行检查点，消息被发送到指示工作者系统执行检查点的多个工作者系统。
-
公开(公告)号：US08793283B1
公开(公告)日：2014-07-29
申请号：US13452275
申请日：2012-04-20
申请人： Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski , Grzegorz Malewicz
发明人： Matthew H. Austern , James C. Dehnert , Aart J. C. Bik , Grzegorz Czajkowski , Grzegorz Malewicz
IPC分类号： G06F17/30
CPC分类号： G06T11/206 , G06F7/00 , G06F8/457 , G06F9/46 , G06F9/5005 , G06F11/1464 , G06F11/1469 , G06F11/2082 , G06F15/17312 , G06F17/30 , G06F17/30958 , G06F17/30961 , G06F2201/84 , G06F2221/0793 , G06N99/00 , G06N99/005 , G06T2210/32 , H04L5/0032 , H04L29/08135 , H04L67/10
摘要： Data are maintained in a distributed computing system that describe a graph. The graph represents relationships among items. The graph has a plurality of vertices that represent the items and a plurality of edges connecting the plurality of vertices. At least one vertex of the plurality of vertices includes a set of label values indicating the at least one vertex's strength of association with a label from a set of labels. The set of labels describe possible characteristics of an item represented by the at least one vertex. At least one edge of the plurality of edges includes a set of label weights for influencing label values that traverse the at least one edge. A label propagation algorithm is executed for a plurality of the vertices in the graph in parallel for a series of synchronized iterations to propagate labels through the graph.
摘要翻译： 数据保存在描述图形的分布式计算系统中。 该图表示各项之间的关系。 该图形具有多个表示项目的顶点和连接多个顶点的多个边缘。 所述多个顶点中的至少一个顶点包括一组标签值，该组标签值指示所述至少一个顶点与来自一组标签的标签的关联强度。 标签集描述由至少一个顶点表示的项目的可能特征。 多个边缘中的至少一个边缘包括用于影响穿过至少一个边缘的标签值的一组标签权重。 针对图形中的多个顶点并行执行标签传播算法，用于一系列同步迭代，以通过图形传播标签。
-
公开(公告)号：US20200349660A1
公开(公告)日：2020-11-05
申请号：US16894761
申请日：2020-06-06
申请人： Grzegorz Malewicz
发明人： Grzegorz Malewicz
摘要： Embodiments relate to searching or comparing sites. One embodiment is a real estate search-or-compare method based on commute durations. The method efficiently processes public transportation and real estate property data to compute the durations of travel between the real estate properties and the vehicle stops. These durations are stored. A request framework is introduced that allows to express a wide range of search-or-compare requests. During request processing, the method identifies parts of the commute paths that depend on any real estate property. Because durations for these parts were precomputed and stored, the method can determine commute durations to every real estate property in a scalable manner. As a result, the method rapidly responds to requests within the real estate market of one of the largest metropolitan areas in existence today. Other embodiments include: searching or comparing based on a monetary cost, transportation using private cars, and sites other than real estate properties. A computer system and a computer service also embody the method.
-
公开(公告)号：US20200348141A1
公开(公告)日：2020-11-05
申请号：US16891104
申请日：2020-06-03
申请人： Grzegorz Malewicz
发明人： Grzegorz Malewicz
摘要： Embodiments relate to producing a plan of a route in a transportation system. The method receives route requirements, including a starting and an ending locations. The method builds a model of the transportation system from data about vehicles. The model abstracts a “prospect travel” between two locations using any of a range of choices of vehicles and walks that can transport between the two locations. Given anticipated wait durations for the vehicles and their ride durations, the method determines an expected minimum travel duration using any of these choices. The method combines the expectations for various locations in a scalable manner. As a result, a route plan that achieves a shortest expected travel duration, and meets other requirements, is computed for one of the largest metropolitan areas in existence today. Other embodiments include a computer system and a product service that implement the method.
-
公开(公告)号：US20210215500A1
公开(公告)日：2021-07-15
申请号：US16940418
申请日：2020-07-28
申请人： Grzegorz Malewicz
发明人： Grzegorz Malewicz
摘要： Embodiments relate to searching or comparing sites. One embodiment is a real estate search-or-compare method based on commute durations. The method efficiently processes public transportation and real estate property data to compute the durations of travel between the real estate properties and the vehicle stops. These durations are stored. A request framework is introduced that allows to express a wide range of search-or-compare requests. During request processing, the method identifies parts of the commute paths that depend on any real estate property. Because durations for these parts were precomputed and stored, the method can determine commute durations to every real estate property in a scalable manner. As a result, the method rapidly responds to requests within the real estate market of one of the largest metropolitan areas in existence today. Other embodiments include: searching or comparing based on a monetary cost, transportation using private cars, and sites other than real estate properties. A computer system and a computer service also embody the method.
-
-
-
-
-
-
-
-
-
搜索结果
21 条记录 (耗时 0.03 秒)
