Способ и сервер для формирования рекомендаций по парковке, отображаемых на электронном устройстве

Изобретение относится к серверу и способу определения рекомендаций по парковке для пункта назначения на карте. Технический результат заключается в повышении релевантности поиска данных. В способе выполняют получение из базы данных с учетом пункта назначения набора прошлых маршрутов, каждый из которых заканчивается в этом пункте назначения, выбранных на карте пользователями, связанными с электронными устройствами; определение сервером набора конечных точек, связанных с набором прошлых маршрутов, каждая из которых представляет собой фактическую конечную точку по меньшей мере одного пользователя электронного устройства, выбравшего прошлый маршрут в этот пункт назначения на карте, и представляет собой возможную рекомендацию по парковке; получение из базы данных графа дорог карты, включающего в себя набор объектов карты, каждый из которых характеризуется местоположением объекта и классом объекта, указывающим на вид структуры данного объекта на карте; кластеризацию сервером набора конечных точек с целью получения набора кластеров, каждый из которых содержит подмножество конечных точек, при этом каждый кластер из по меньшей мере части набора кластеров связан с по меньшей мере одним объектом карты и с местоположением этого объекта, а кластеризация выполняется на основе: пункта назначения, конечных точек, местоположений объекта и классов объектов карты; получение от электронного устройства запроса текущего маршрута в пункт назначения, включающего в себя указание на пункт отправления; определение сервером текущего маршрута на карте из пункта отправления в пункт назначения и по меньшей мере одного кластера, содержащего подмножество конечных точек, в качестве рекомендации по парковке для этого пункта назначения; и отправку электронному устройству текущего маршрута, включающего в себя рекомендацию по парковке. 2 н. и 20 з.п. ф-лы, 7 ил.

 

Область техники, к которой относится изобретение

[1] Настоящая технология относится к выполняемым электронным устройством приложениям, связанным с картами, в частности, к способу и серверу для формирования рекомендаций по парковке в пункте назначения в приложении карты, выполняемом электронным устройством.

Уровень техники

[2] Многие доступные пользователю электронные устройства предоставляют геолокационную и маршрутную информацию путем выполнения «приложения карты». [3] Некоторые из таких электронных устройств предназначены для предоставления геолокационной и маршрутной информации. В качестве примера такого устройства можно привести портативный GPS-навигатор, например, поставляемый компанией TomTom Corporation (Амстердам, Нидерланды). В качестве другого примера такого устройства можно привести GPS-навигатор, встроенный в автомобиль. В частности, многие автопроизводители по заказу встраивают в свои автомобили навигационные системы.

[4] Другие электронные устройства предоставляют геолокационную и маршрутную информацию в качестве дополнения к другим функциям. Например, большинство доступных в настоящее время на рынке смартфонов содержит приложение, обеспечивающее геолокацию и маршрутизацию. Некоторые из этих приложений карт являются «родными» для смартфона, т.е. входят в состав операционной системы или набора предустановленных приложений. Другие приложения карт могут быть загружены из репозиториев приложений (т.е. из так называемых «магазинов приложений», таких как APPLE™ STORE и т.п.).

[5] Большинство приложений карт позволяет пользователю проложить маршрут из пункта А (пункт отправления) в пункт Б (пункт назначения). В зависимости от конкретной реализации приложения карты, пользователь также может выбрать дополнительные варианты, такие как самый быстрый маршрут, самый короткий маршрут, маршрут без автомагистралей, маршрут без платных дорог и т.д. После того, как пользователь сделал свой выбор, приложение карты с учетом предпочтений пользователя формирует один или несколько предлагаемых пользователю на выбор маршрутов из пункта А в пункт Б.

[6] Когда пользователь начинает движение по одному из предложенных маршрутов, приложение карты обычно отображает процесс движения пользователя по этому маршруту (чаще всего путем перемещения стрелки или другого символа, обозначающего положение пользователя на предложенном маршруте). Приложение карты также может предоставлять пользователю дополнительную информацию, например, время до прибытия в пункт назначения, информацию о препятствиях на маршруте (таких как дорожно-транспортные происшествия или места строительно-ремонтных работ), информацию о дорожном движении на маршруте, альтернативные маршруты (для их отображения обычно используется «менее заметное выделение», например, серым цветом) и т.п.

[7] При приближении к пункту назначения (т.е. к пункту Б) пользователь должен найти парковочное место, чтобы оставить свой автомобиль. В зависимости от местоположения пункта Б (например, деловой район города или пригород, и т.д.), поиск парковочного места может оказаться непростой задачей для пользователя. На поиски парковочного места пользователь может потратить много времени. В существующих вариантах реализации приложений карт очень мало внимания уделяется рекомендациям пользователю относительно возможных парковочных мест. Наиболее распространенное в настоящее время решение заключается в том, что приложение карты отображает на карте местоположение крытых паркингов и т.п.

[8] В патентной заявке US 20160155276 A1 «Method and Apparatus of Dynamically Assigning Parking Lot» (Institute for Information Industry, опубликована 1 декабря 2014 г.) описан способ динамического выделения парковочного места. Сначала в соответствии с пунктом назначения, сообщенным автомобилем, выбирается одна или несколько парковочных мест, расположенных на заданном расстоянии от него. Затем время, когда будет доступно парковочное место, оценивается в соответствии с актуальными парковочными данными и предысторией парковки на одном или нескольких парковочных местах. Затем в зависимости от времени, когда будет доступно парковочное место, и информации о количестве автомобилей в очереди на одно или несколько парковочных мест, оценивается время ожидания. В зависимости от местоположения автомобиля оценивается время движения автомобиля до одного или нескольких парковочных мест. В конце оценивается общее время ожидания в соответствии с временем движения и временем ожидания для одного или несколько парковочных мест.

[9] В патенте US 9652986 A1 «Method for providing parking information on free parking spaces» (Bayerische Motoren Werke AG, выдан 16 мая 2017 г.) описан способ предоставления парковочной информации о свободных парковочных местах в пределах по меньшей мере одного городского квартала. Способ обеспечивает обнаружение информации о свободных парковочных местах, на основании которой формируется база знаний предыстории. Предыстория для конкретных городских кварталов и/или для конкретных моментов времени либо периодов времени содержит статистические данные относительно свободных парковочных мест. На основании предыстории и текущей информации, полученной движущимися транспортными средствами в первый момент времени для одного или нескольких выбранных городских кварталов, определяется распределение вероятности наличия свободных парковочных мест для этих одного или нескольких городских кварталов и формируется визуальное представление этого распределения вероятности, соответствующее парковочной информации относительно свободных парковочных мест в пределах одного или нескольких городских кварталов.

Раскрытие изобретения

[10] Варианты осуществления настоящей технологии разработаны на основе понимания разработчиками желательности того, чтобы приложение карты формировало рекомендации по парковке при приближении транспортного средства пользователя к пункту назначения на маршруте, сформированном приложением карты.

[11] В частности, разработчики обнаружили, что пользователи могут парковать свои транспортные средства в местах, которые могут быть не указаны в приложениях карт и/или могут быть неизвестными им. Кроме того, такие места могут быть неофициальными и более дешевыми (или бесплатными) и могут быть более удобными для пользователей по сравнению с обычно рекомендуемыми местами.

[12] Разработчики также обнаружили, что операторам приложений карт доступна предыстория пользователей, которые двигались в некоторый пункт назначения по маршрутам, сформированным приложениями карт, и данные о таких прошлых действиях пользователей могут быть использованы для определения возможных парковочных мест.

[13] Кроме того, разработчики также определили, что некоторые известные способы при предоставлении рекомендаций по парковке не учитывают иерархию объектов на карте и могут предоставлять рекомендации по парковке, которые могут быть неудобными в реализации, дорогостоящими или соответствовать постоянно занятым местам.

[14] Настоящая технология основана на понимании разработчиками того, что алгоритм поиска минимального покрывающего дерева (MST, Minimum Spanning Tree) может быть модифицирован для иерархической кластеризации парковочных мест так, чтобы парковочные места могли быть указаны пользователям в качестве рекомендаций для пункта назначения более эффективно, путем рассмотрения различных признаков и ограничений, таких как местоположение, наличие препятствий, недоступные места, цена парковки и т.п., при формировании набора кластеров.

[15] Таким образом, варианты осуществления настоящей технологии относятся к способу и серверу для формирования рекомендаций по парковке для пункта назначения в виде кластеров, предназначенных для отображения на электронном устройстве, с использованием алгоритма иерархической кластеризации.

[16] Согласно первому аспекту настоящей технологии реализован компьютерный способ определения указываемых на карте рекомендаций по парковке для пункта назначения на карте, отображаемой на электронном устройстве. Способ выполняется сервером, связанным с электронным устройством и с базой данных и выполняющим алгоритм кластеризации. Способ, в зависимости от пункта назначения, начинается с получения из базы данных набора прошлых маршрутов, выбранных на карте пользователями, связанными с электронными устройствами, каждый из которых заканчивается в этом пункте назначения. Затем определяется набор конечных точек, связанных с набором прошлых маршрутов, каждая из которых представляет собой фактическую конечную точку по меньшей мере одного пользователя электронного устройства, выбравшего прошлый маршрут в этот пункт назначения на карте, и представляет собой возможную рекомендацию по парковке. Затем формируется граф дорог для карты, включающий в себя набор объектов карты, каждый из которых характеризуется местоположением объекта и классом объекта, указывающим на вид структуры на карте. Набор конечных точек разделяется на кластеры с целью получения набора кластеров, каждый из которых содержит подмножество конечных точек, при этом каждый кластер из по меньшей мере части набора кластеров связан с по меньшей мере одним объектом карты и с местоположением этого объекта, а кластеризация выполняется с учетом пункта назначения, конечных точек, местоположений объектов и классов объектов карты. Из клиентского устройства принимается запрос текущего маршрута в пункт назначения, включающий в себя указание на пункт отправления. Далее определяется текущий маршрут на карте из пункта отправления в пункт назначения и с учетом пункта назначения определяется по меньшей мере один кластер, содержащий подмножество конечных точек, в качестве рекомендации по парковке для этого пункта назначения. Текущий маршрут, включающий в себя рекомендацию по парковке, отправляется электронному устройству.

[17] В некоторых вариантах осуществления способа набор конечных точек определяется так, чтобы расстояние между каждой конечной точкой и пунктом назначения было меньше заранее заданного порогового значения.

[18] В некоторых вариантах осуществления способа класс объекта указывает на иерархический уровень объекта карты на графе дорог, а кластеризация выполняется в иерархическом порядке.

[19] В некоторых вариантах осуществления способа каждый кластер характеризуется центроидом и размером, а по меньшей мере один кластер, содержащий подмножество конечных точек в качестве рекомендации по парковке, определяется на основе центроида и размера по меньшей мере одного кластера.

[20] В некоторых вариантах осуществления способа кластеризация выполняется с использованием функции эвристической оценки.

[21] В некоторых вариантах осуществления способа алгоритм кластеризации основан на алгоритме Крускала (Kruskal).

[22] В некоторых вариантах осуществления способа набор кластеров содержит заранее заданное количество кластеров.

[23] В некоторых вариантах осуществления способа каждый прошлый маршрут связан с периодом времени, проведенного по меньшей мере одним пользователем электронного устройства в конечной точке, а определение набора конечных точек дополнительно зависит от превышения этим периодом времени заранее заданного порогового значения времени.

[24] В некоторых вариантах осуществления способа он, до кластеризации, дополнительно включает в себя сопоставление сервером каждой конечной точки из по меньшей мере части набора конечных точек с по меньшей мере одним объектом карты с учетом расстояния между конечной точкой и по меньшей мере одним местоположением объекта, связанным с каждым объектом карты.

[25] В некоторых вариантах осуществления способа класс объекта представляет собой «участок дороги», «препятствие» или «известное парковочное место».

[26] В некоторых вариантах осуществления способа класс «участок дороги» включает в себя скоростную автостраду, автомагистраль, дорогу районного значения или местную дорогу.

[27] Согласно другому аспекту настоящей технологии реализован сервер для определения указываемых на карте рекомендаций по парковке для пункта назначения на карте, отображаемой на электронном устройстве, связанном с сервером. Сервер связан с базой данных и содержит процессор и машиночитаемый физический носитель информации, содержащий команды. Процессор при исполнении команд способен с учетом пункта назначения получать из базы данных набор прошлых маршрутов, выбранных на карте пользователями, связанными с электронными устройствами, каждый из которых заканчивается в этом пункте назначения. Процессор способен определять набор конечных точек, связанных с набором прошлых маршрутов, каждая из которых представляет собой фактическую конечную точку по меньшей мере одного пользователя электронного устройства, выбравшего прошлый маршрут в этот пункт назначения на карте, и представляет собой возможную рекомендацию по парковке. Затем процессор способен получать из базы данных граф дорог для карты, содержащий набор объектов карты, каждый из которых характеризуется местоположением объекта и классом объекта, указывающим на вид структуры на карте. Процессор способен разделять набор конечных точек на кластеры с целью получения набора кластеров, каждый из которых содержит подмножество конечных точек, при этом каждый кластер из по меньшей мере части набора кластеров связан с по меньшей мере одним объектом карты и с местоположением этого объекта, а кластеризация основана на пункте назначения, конечных точках, местоположениях объектов и классах объектов карты. Процессор способен получать из электронного устройства запрос текущего маршрута в пункт назначения, включающий в себя указание на пункт отправления. Процессор способен определять текущий маршрут на карте из пункта отправления в пункт назначения и по меньшей мере один кластер, содержащий подмножество конечных точек, в качестве рекомендации по парковке для этого пункта назначения, а также отправлять клиентскому устройству текущий маршрут, включающий в себя рекомендацию по парковке.

[28] В некоторых вариантах осуществления сервера набор конечных точек определяется так, чтобы расстояние между каждой конечной точкой и пунктом назначения было меньше заранее заданного порогового значения.

[29] В некоторых вариантах осуществления сервера класс объекта указывает на иерархический уровень объекта карты на графе дорог, а кластеризация выполняется в иерархическом порядке.

[30] В некоторых вариантах осуществления сервера каждый кластер характеризуется центроидом и размером. Определение по меньшей мере одного кластера, содержащего подмножество конечных точек, в качестве рекомендации по парковке основано на центроиде и размере по меньшей мере одного кластера.

[31] В некоторых вариантах осуществления сервера кластеризация выполняется с использованием функции эвристической оценки.

[32] В некоторых вариантах осуществления сервера алгоритм кластеризации основан на алгоритме Крускала.

[33] В некоторых вариантах осуществления сервера набор кластеров содержит заранее заданное количество кластеров.

[34] В некоторых вариантах осуществления сервера каждый прошлый маршрут связан с периодом времени, проведенного по меньшей мере одним пользователем электронного устройства в конечной точке. Определение набора конечных точек дополнительно зависит от превышения этим периодом времени заранее заданного порогового значения времени.

[35] В некоторых вариантах осуществления сервера процессор до кластеризации дополнительно способен сопоставлять каждую конечную точку из по меньшей мере части набора конечных точек с по меньшей мере одним объектом карты с учетом расстояния между конечной точкой и по меньшей мере одним местоположением объекта, связанным с каждым объектом карты.

[36] В некоторых вариантах осуществления сервера класс объекта представляет собой «участок дороги», «препятствие» или «известное парковочное место».

[37] В некоторых вариантах осуществления сервера класс «участок дороги» включает в себя скоростную автостраду, автомагистраль, дорогу районного значения или местную дорогу. В контексте настоящего описания термин «сервер» означает компьютерную программу, выполняемую соответствующими аппаратными средствами и способную принимать запросы (например от клиентских устройств) через сеть и выполнять эти запросы или инициировать их выполнение. Аппаратные средства могут быть реализованы в виде одного физического компьютера или одной компьютерной системы, что не существенно для настоящей технологии. В настоящем контексте выражение «сервер» не означает, что каждая задача (например, принятая команда или запрос) или какая-либо определенная задача принимается, выполняется или запускается одним и тем же сервером (т.е. одними и теми же программными и/или аппаратными средствами). Это выражение означает, что любое количество программных средств или аппаратных средств может принимать, отправлять, выполнять или инициировать выполнение любой задачи или запроса, либо результатов любых задач или запросов. Все эти программные и аппаратные средства могут представлять собой один сервер или несколько серверов, причем в выражении «по меньшей мере один сервер» подразумеваются оба эти случая.

[38] В контексте настоящего описания термин «электронное устройство» означает любое компьютерное аппаратное средство, способное выполнять программы, подходящие для решения поставленной задачи. В контексте настоящего описания термин «электронное устройство» подразумевает, что устройство может функционировать в качестве сервера для других электронных устройств и клиентских устройств, тем не менее, это не обязательно для настоящей технологии. Таким образом, некоторые (не имеющие ограничительного характера) примеры электронных устройств включают в себя персональные компьютеры (настольные, ноутбуки, нетбуки и т.п.), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Должно быть понятно, что в настоящем контексте тот факт, что устройство функционирует в качестве электронного устройства, не означает, что оно не может функционировать в качестве сервера для других электронных устройств. Использование выражения «электронное устройство» не исключает использования нескольких клиентских устройств для приема, отправки, выполнения или инициирования выполнения любой задачи или запроса, либо результатов любых задач или запросов, либо шагов любого описанного здесь способа.

[39] В контексте настоящего описания термин «клиентское устройство» означает любое компьютерное аппаратное средство, способное выполнять программы, подходящие для решения поставленной задачи. В контексте настоящего описания термин «клиентское устройство» в общем случае связан с пользователем клиентского устройства. Таким образом, некоторые (не имеющие ограничительного характера) примеры клиентских устройств включают в себя персональные компьютеры (настольные, ноутбуки, нетбуки и т.п.), смартфоны и планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует отметить, что в данном контексте устройство, функционирующее как клиентское устройство, также может функционировать как сервер для других клиентских устройств. Использование выражения «клиентское устройство» не исключает использования нескольких клиентских устройств для приема, отправки, выполнения или инициирования выполнения любой задачи или запроса либо результатов любых задач или запросов, либо шагов любого описанного здесь способа.

[40] В контексте настоящего описания выражение «информация» включает в себя информацию любого рода или вида, допускающую хранение в базе данных. Таким образом, информация включает в себя аудиовизуальные произведения (изображения, фильмы, звукозаписи, презентации и т.д.), данные (данные о местоположении, числовые данные и т.д.), текст (мнения, комментарии, вопросы, сообщения и т.д.), документы, электронные таблицы и т.д., но не ограничивается ими.

[41] В контексте настоящего описания выражение «программный компонент» обозначает программное обеспечение (подходящее для определенных аппаратных средств), необходимое и достаточное для выполнения определенной функции или нескольких функций.

[42] В контексте настоящего описания выражение «носитель компьютерной информации» (также называется «носителем информации») означает носители любого типа и вида, включая ОЗУ, ПЗУ, диски (CD-ROM, DVD, гибкие диски, жесткие диски и т.д.), USB-накопители, твердотельные накопители, накопители на магнитных лентах и т.д. Для формирования носителя компьютерной информации может объединяться множество элементов, включая два или более элементов носителя информации одного вида и/или два или более элементов носителей информации различных видов.

[43] В контексте настоящего описания термин «база данных» означает любой структурированный набор данных, независимо от его конкретной структуры, программного обеспечения для управления базой данных или компьютерных аппаратных средств для хранения этих данных, их применения или обеспечения их использования иным способом. База данных может располагаться в тех же аппаратных средствах, где реализован процесс, обеспечивающий хранение или использование информации, хранящейся в базе данных, либо база данных может располагаться в отдельных аппаратных средствах, таких как специализированный сервер или множество серверов.

[44] В контексте настоящего описания числительные «первый» «второй», «третий» и т.д. используются лишь для указания различия между существительными, к которым они относятся, но не для описания каких-либо определенных взаимосвязей между этими существительными. Например, должно быть понятно, что использование терминов «первый сервер» и «третий сервер» не подразумевает какого-либо определенного порядка, типа, хронологии, иерархии или классификации, в данном случае, серверов, а также что их использование (само по себе) не подразумевает наличие «второго сервера» в любой ситуации. Кроме того, как встречается в настоящем описании в другом контексте, ссылка на «первый» элемент и «второй» элемент не исключает того, что эти два элемента в действительности могут быть одним и тем же элементом. Таким образом, например, в некоторых случаях «первый» сервер и «второй» сервер могут представлять собой один и тот же элемент программных и/или аппаратных средств, а в других случаях - различные элементы программных и/или аппаратных средств.

[45] Каждый вариант осуществления настоящей технологии относится к по меньшей мере одной из вышеупомянутых целей и/или аспектов, но не обязательно ко всем ним. Должно быть понятно, что некоторые аспекты настоящей технологии, связанные с попыткой достижения вышеупомянутой цели, могут не соответствовать этой цели и/или могут соответствовать другим целям, явным образом здесь не упомянутым.

[46] Дополнительные и/или альтернативные признаки, аспекты и преимущества вариантов осуществления настоящей технологии содержатся в дальнейшем описании, в приложенных чертежах и в формуле изобретения.

Краткое описание чертежей

[47] Эти и другие признаки, аспекты и преимущества настоящей технологии поясняются в дальнейшем описании, приложенной формуле изобретения и на следующих чертежах.

[48] На фиг. 1 представлена схема примера компьютерной системы для реализации некоторых вариантов осуществления систем и/или способов согласно настоящей технологии.

[49] На фиг. 2 представлена схема сетевой компьютерной среды, пригодной для использования в соответствии с не имеющими ограничительного характера вариантами осуществления настоящей технологии.

[50] На фиг. 3 представлен набор прошлых маршрутов в пункт назначения, выбранных пользователями на фрагменте карты в соответствии с не имеющими ограничительного характера вариантами осуществления настоящей технологии.

[51] На фиг. 4 представлена схема соответствующей не имеющим ограничительного характера вариантам осуществления настоящей технологии процедуры 400 кластеризации.

[52] На фиг. 5 представлен фрагмент карты с набором кластеров в качестве рекомендаций по парковке в соответствии с не имеющими ограничительного характера вариантами осуществления настоящей технологии.

[53] На фиг. 6 представлена блок-схема соответствующего не имеющим ограничительного характера вариантам осуществления настоящей технологии способа определения рекомендаций по парковке для пункта назначения.

[54] На фиг. 7 представлена блок-схема способа предоставления пользователю электронного устройства рекомендаций по парковке для пункта назначения. Осуществление изобретения

[55] Представленные в данном описании примеры и условный язык предназначены для обеспечения лучшего понимания принципов настоящей технологии, а не для ограничения ее объема до таких специально приведенных примеров и условий. Очевидно, что специалисты в данной области техники могут разработать различные способы и устройства, которые явно не описаны и не показаны, но осуществляют принципы настоящей технологии в пределах ее существа и объема.

[56] Кроме того, чтобы способствовать лучшему пониманию, последующее описание может содержать упрощенные варианты реализации настоящей технологии. Специалисту в данной области должно быть понятно, что различные варианты осуществления данной технологии могут быть значительно сложнее.

[57] В некоторых случаях также приводятся полезные примеры модификаций настоящей технологии. Они способствуют пониманию, но также не определяют объема или границ данной технологии. Представленный перечень модификаций не является исчерпывающим и специалист в данной области может разработать и другие модификации в пределах объема настоящей технологии. Кроме того, если в некоторых случаях модификации не описаны, это не означает, что они невозможны и/или что описание содержит единственный вариант реализации того или иного элемента настоящей технологии.

[58] Более того, описание принципов, аспектов и вариантов реализации настоящей технологии, а также их конкретные примеры предназначены для охвата их структурных и функциональных эквивалентов, независимо от того, известны они в настоящее время или будут разработаны в будущем. Например, специалистам в данной области техники должно быть понятно, что любые описанные структурные схемы соответствуют концептуальным представлениям иллюстративных принципиальных схем, реализующих принципы настоящей технологии. Также должно быть очевидно, что любые блок-схемы, схемы процессов, диаграммы изменения состояния, псевдокоды и т.п.соответствуют различным процессам, которые могут быть представлены на машиночитаемом физическом носителе информации и могут выполняться компьютером или процессором, независимо от того, показан явно такой компьютер или процессор либо нет.

[59] Функции различных элементов, показанных на чертежах, включая любой функциональный блок, обозначенный как «процессор», могут реализовываться с использованием специализированных аппаратных средств, а также аппаратных средств, способных выполнять соответствующее программное обеспечение. Если используется процессор, его функции могут выполняться одним выделенным процессором, одним совместно используемым процессором или множеством отдельных процессоров, некоторые из которых могут использоваться совместно. Кроме того, явное использование термина «процессор» или «контроллер» не должно трактоваться как указание исключительно на аппаратные средства, способные выполнять программное обеспечение, и может, помимо прочего, подразумевать аппаратные средства цифрового сигнального процессора (DSP), сетевой процессор, специализированную интегральную схему (ASIC), программируемую вентильную матрицу (FPGA), ПЗУ для хранения программного обеспечения, ОЗУ и энергонезависимое ЗУ. Также могут подразумеваться другие аппаратные средства, общего назначения и/или заказные.

[60] Программные модули или просто модули, реализация которых подразумевается в виде программных средств, могут быть представлены здесь как любое сочетание элементов блок-схемы или других элементов, указывающих на выполнение шагов процесса и/или содержащих их текстовое описание. Такие модули могут выполняться аппаратными средствами, показанными явно или предполагаемыми.

[61] Учитывая вышеизложенные принципы, далее рассмотрены некоторые не имеющие ограничительного характера примеры, иллюстрирующие различные варианты реализации аспектов настоящей технологии.

[62] Описание системы

[63] На фиг. 1 представлена компьютерная система 100, пригодная для использования в некоторых вариантах осуществления настоящей технологии и содержащая различные элементы аппаратных средств, включая один или несколько одно- или многоядерных процессоров, которые совместно представлены процессором 110, твердотельный накопитель 120, память 130, которая может представлять собой ОЗУ, сетевой модуль 140 и модуль 150 GPS. Связь между элементами компьютерной системы 100 может осуществляться через одну или несколько внутренних и/или внешних шин (с общим обозначением 102), таких как шина PCI, универсальная последовательная шина, шина Fire Wire стандарта IEEE 1394, шина SCSI, шина Serial-ATA и т.д., с которыми аппаратные элементы соединены электронным образом. В представленном на фиг. 1 не имеющем ограничительного характера варианте осуществления изобретения связь в компьютерной системе 100 реализована с использованием звездообразной структуры через процессор 110. Тем не менее, в альтернативных вариантах осуществления настоящей технологии связь может быть реализована иным образом.

[64] Согласно вариантам осуществления настоящей технологии, твердотельный накопитель 120 хранит программные команды, пригодные для загрузки в память 130 и исполнения процессором 110 с целью отображения информации пользователю компьютерной системы 100, как более подробно описано ниже. Например, программные команды могут входить в состав приложения карты или навигационного приложения, выполняемого процессором 110. Сетевой модуль 140 и модуль 150 GPS обеспечивают связь между различными компьютерными системами, серверами и/или другими устройствами.

[65] На фиг. 2 представлена сетевая компьютерная среда 200, пригодная для использования с некоторыми вариантами осуществления систем и/или способов согласно настоящей технологии. Сетевая компьютерная среда 200 содержит множество 202 электронных устройств. Множество 202 электронных устройств содержит первое электронное устройство 204, второе электронное устройство 210 и третье электронное устройство 216, связанные с первым пользователем 206, со вторым пользователем 212 и с третьим пользователем 218, соответственно. Первый пользователь 206 управляет первым транспортным средством 208, второй пользователь 212 управляет вторым транспортным средством 214, третий пользователь 218 управляет третьим транспортным средством 220. [66] Следует отметить, что несмотря на то, что множество 202 электронных устройств показано как содержащее три электронных устройства, это не обязательно для каждого варианта реализации настоящей технологии. На практике множество 202 электронных устройств может содержать десятки или сотни тысяч устройств.

[67] Сетевая компьютерная среда 200 также содержит сервер 230, связанный со множеством 202 электронных устройств через сеть 240 связи. Сетевая компьютерная среда 200 также содержит спутник 250 системы GPS, передающий сигнал 260 системы GPS и/или принимающий его от множества 202 электронных устройств. Должно быть понятно, что настоящая технология не ограничивается системой GPS и может использовать технологию определения местоположения, отличную от системы GPS (например, ГЛОНАСС, DORIS, BeiDou или COMPASS).

[68] В некоторых вариантах осуществления настоящей технологии сеть 240 связи представляет собой сеть Интернет. В альтернативных не имеющих ограничительного характера вариантах осуществления изобретения сеть связи может быть реализована в виде любой подходящей локальной сети (LAN, Local Area Network), глобальной сети (WAN, Wide Area Network), частной сети связи и т.п.Очевидно, что варианты осуществления сети связи приведены только в иллюстративных целях. Реализация линии связи (отдельно не обозначена) между электронным устройством и сетью 240 связи зависит, среди прочего, от реализации электронного устройства.

[69] В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 230 реализован в виде традиционного компьютерного сервера. В одном не имеющем ограничительного характера примере сервер 230 реализован в виде сервера Dell™ PowerEdge™, работающего под управлением операционной системы Microsoft™ Windows Server™, но он также может быть реализован с использованием любых других подходящих аппаратных средств, прикладного программного обеспечения и/или встроенного программного обеспечения, либо их сочетания. В представленных не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 230 представляет собой один сервер. В других не имеющих ограничительного характера вариантах осуществления настоящей технологии (не показаны) функции сервера 230 могут быть распределены между несколькими серверами.

[70] На реализацию электронного устройства из множества 202 электронных устройств не накладывается каких-либо особых ограничений. Например, электронное устройство может быть реализовано в виде беспроводного устройства связи, такого как мобильный телефон (например, смартфон или радиотелефон), автомобильного навигатора (например, TomTom™ или Garmin™), планшета, персонального компьютера и т.п. Тем не менее, на фиг. 2 каждое электронное устройство показано в виде смартфона (несмотря на то, что они не обязательно должны быть реализованы одинаково и что каждое электронное устройство может быть реализовано на основе другого электронного устройства). Кроме того, в некоторых вариантах осуществления настоящей технологии электронное устройство может быть интегрировано в транспортное средство в виде встроенного мультимедийного компьютера (MCU, Media Computer Unit).

[71] Электронное устройство может содержать некоторые или все элементы компьютерной системы 100, представленной на фиг. 1. В некоторых вариантах осуществления изобретения электронное устройство содержит сетевой модуль 140 для связи с сервером 230 через сеть 240 связи, модуль 150 GPS для приема от спутника 250 системы GPS и передачи на него сигнала 260 системы GPS (т.е. для обеспечения функций GPS электронного устройства), процессор 110, память 130 и интерфейс отображения информации, например, сенсорный экран. Электронное устройство содержит аппаратные средства и/или прикладное программное обеспечение и/или встроенное программное обеспечение либо их сочетание для выполнения приложения карты, лишь один экземпляр которого показан на фиг. 2 в позиции 280 в сочетании с третьим электронным устройством 216. В некоторых вариантах осуществления настоящей технологии электронное устройство может быть способным дополнять информацию GPS с использованием позиционирования на основе беспроводной сети, когда географическое местоположение определяется на основе наличия конкретных беспроводных сетей, ближайших к пользовательскому устройству (например, Wi-Fi-позиционирование). [72] В конкретном не имеющем ограничительного характера варианте осуществления настоящей технологии приложение 280 карты может быть реализовано в виде приложений Yandex.Maps™ или Yandex.Navigator™, поставляемых компанией Yandex^®.

[73] Приложение 280 карты способно к двухсторонней связи с сервером 230. Сервер 230 способен выполнять серверное приложение 282 карты. Приложение 280 карты и серверное приложение 282 карты способны предоставлять пользователю (такому как третий пользователь 218) карту и маршрутную информацию. В некоторых вариантах осуществления настоящей технологии приложение 280 карты способно формировать и отправлять серверу 230 запрос 236 карты, содержащий информацию о запрошенных третьим пользователем 218 картографических данных (такую как адрес для отображения конкретной интересующей точки или маршрутную информацию для формирования маршрута). Запрос 236 карты может быть сформирован в ответ на взаимодействие третьего пользователя 218 с приложением 280 карты (например, ввод запроса на информацию и т.д.). В ответ на получение запроса 236 карты сервер 230 может сформировать и отправить приложению 280 карты пакет 238 картографических данных, содержащий данные, необходимые приложению 280 карты для формирования и отображения карты, соответствующей информации, запрошенной третьим пользователем 218, и отправленной в качестве части запроса 236 карты.

[74] В других вариантах осуществления настоящей технологии приложение 280 карты может локально (т.е. в третьем электронном устройстве 216) хранить некоторые картографические данные для так называемого автономного просмотра (т.е. для формирования картографических данных без отправки запроса 236 карты и/или без получения пакета 238 картографических данных). Иными словами, в общем случае приложение 280 карты может выполнять приложение карты либо на основе локально хранящейся информации, либо на основе информации, полученной от сервера 230 в реальном времени.

[75] На фиг. 3 представлена соответствующая не имеющим ограничительного характера вариантам осуществления настоящей технологии схема фрагмента 300 карты, включающего в себя набор 310 прошлых маршрутов в пункт 312 назначения, выбранных множеством пользователей (таких как первый пользователь 206, второй пользователь 212 и третий пользователь 218).

[76] Следует отметить, что серверное приложение 282 карты не обязательно должно иметь графический интерфейс пользователя (GUI, Graphical User Interface) и что набор 310 прошлых маршрутов представлен на фрагменте 300 карты для иллюстрации и лучшего понимания.

[77] Набор прошлых маршрутов

[78] Сервер 230 с учетом пункта 312 назначения получает из базы 235 данных набор 310 прошлых маршрутов из пунктов 308 отправления в пункт 312 назначения, выбранных множеством пользователей (таких как первый пользователь 206, второй пользователь 212 и третий пользователь 218), связанных с множеством 202 электронных устройств. Каждый прошлый маршрут 314 из набора 310 прошлых маршрутов представляет собой прошлый маршрут, запрошенный пользователем через приложение 280 карты на электронном устройстве (например, на втором электронном устройстве 210). Серверное приложение 282 карты на сервере 230 могло отправлять пакет 238 картографических данных и инициировать отображение в приложении 280 карты каждого электронного устройства (например, второго электронного устройства 210) прошлого маршрута 314 в пункт 312 назначения с учетом пункта 308 отправления электронного устройства (например, второго электронного устройства 210). Затем каждый пользователь мог проследовать по прошлому маршруту 314 из пункта 308 отправления в пункт 312 назначения на своем транспортном средстве.

[79] Набор 310 прошлых маршрутов может быть извлечен для конкретного периода времени (например, с понедельника по пятницу между 8:00 и 17:00 для периода с января по август) или для всего периода (например, все маршруты в пункт 312 назначения с января по декабрь). Количество прошлых маршрутов в наборе 310 прошлых маршрутов не ограничено и может составлять сотни, тысячи и более маршрутов. В некоторых вариантах осуществления настоящей технологии сервер 230 может извлекать набор 310 прошлых маршрутов с учетом пункта 312 назначения, только если количество прошлых маршрутов в наборе 310 прошлых маршрутов превышает заранее заданное пороговое значение (например, по меньшей мере 2000 прошлых маршрутов).

[80] На характер пункта 312 назначения не накладывается каких-либо ограничений. Пункт 312 назначения может представлять собой интересующую точку (POI, Point Of Interest), выбранную или введенную в приложении 280 карты множества 202 электронных устройств, такую как жилое здание, предприятие, больница, парк и т.п.В других вариантах осуществления настоящей технологии пункт 312 назначения может быть введен путем указания адреса или географических координат в серверном приложении 282 карты. В других вариантах осуществления настоящей технологии пункт 312 назначения может представлять собой частный дом (например, на одну семью) или частный земельный участок.

[81] Каждый прошлый маршрут 314 из набора 310 прошлых маршрутов также может включать в себя промежуточные пункты 316, которые представляют собой пункты на прошлом маршруте 314, выбранные электронным устройством (например, вторым электронным устройством 210) каждого пользователя с целью прибытия в пункт 312 назначения с использованием транспортных средств (например, первого транспортного средства 208). Пункты 308 отправления, пункт 312 назначения и промежуточные пункты 316 могут быть связаны с отметками времени, указывающими на то, в какое время пользователь был в соответствующем пункте.

[82] Набор конечных точек

[83] Серверное приложение 282 карты определяет для каждого прошлого маршрута 314 из набора 310 прошлых маршрутов конечную точку 324 с целью получения набора 320 конечных точек. Конечная точка 324 указывает на фактическую конечную точку пользователя (например, второго пользователя 212) электронного устройства (например, третьего электронного устройства 216), проследовавшего по прошлому маршруту 314 на транспортном средстве (например, на втором транспортном средстве 214). Очевидно, что пользователю (например, второму пользователю 212), который намерен достичь пункта 312 назначения по прошлому маршруту 314 на транспортном средстве (например, на втором транспортном средстве 214) может потребоваться припарковать транспортное средство рядом с пунктом 312 назначения, и пользователь обычно останавливает или паркует свое транспортное средство в конечной точке 324 на расстоянии пешей доступности от пункта 312 назначения.

[84] На способ определения серверным приложением 282 карты конечной точки 324 не накладывается каких-либо ограничений.

[85] В некоторых вариантах осуществления настоящей технологии серверное приложение 282 карты может определять конечную точку 324 на основе заранее заданного порогового значения времени и/или заранее заданного порогового значения расстояния до пункта 312 назначения. Например, если электронное устройство (например, третье электронное устройство 216) пользователя (например, второго пользователя 212) находилось в пределах порогового значения расстояния 500 метров от пункта назначения более 4 минут, то серверное приложение 282 карты может рассматривать это место как конечную точку 324. Заранее заданное пороговое значение времени может быть выбрано для выявления ситуаций, когда второй пользователь 212 остановил свое второе транспортное средство 214 в конечной точке 324 только временно, например, на светофоре. Дополнительно или в качестве альтернативы, для определения места в качестве конечной точки 324 может быть необходимо, чтобы количество пользователей, связанных с прошлыми маршрутами и остановившихся в этом месте, превышало заранее заданное пороговое значение. Например, может быть необходимо, чтобы по меньшей мере 10 пользователей, проследовавших по прошлым маршрутам в пункт назначения 312, остановились в определенном месте, чтобы это место рассматривалось в качестве конечной точки для пункта назначения 312.

[86] В других вариантах осуществления настоящей технологии приложение 280 карты третьего электронного устройства 216 может отправлять указание на местоположение серверному приложению 282 карты, например, когда второй пользователь 212 закрывает приложение 280 карты на третьем электронном устройстве и/или переключается на другое приложение (не показано) на третьем электронном устройстве 216, что может указывать на то, что пользователь (например, второй пользователь 212) завершил движение на своем втором транспортном средстве 214 в пункт назначения 312, и инициировать отправку запроса 236 карты. Дополнительно или в качестве альтернативы, пользователь (например, второй пользователь 212) может указать в приложении 280 карты, что он завершил движение, что инициирует отправку приложением 280 карты последнего местоположения серверному приложению 282 карты. Таким образом, конечная точка 324 может быть расположена до пункта 312 назначения (например, в промежуточном пункте из набора 316 промежуточных пунктов на прошлом маршруте 314), после пункта 312 назначения на прошлом маршруте 314 (т.е. за пунктом 312 назначения в направлении, противоположном прошлому маршруту 314) или непосредственно в пункте 312 назначения.

[87] В общем случае конечная точка 324 представляет собой «неофициальное» парковочное место, т.е. конечная точка 324 отсутствует в базе 235 данных сервера 230 в качестве парковочного места. Тем не менее, это не обязательно должно быть именно так в каждом варианте осуществления настоящей технологии и официальные парковочные места, такие как платные муниципальные или частные парковочные места, также могут рассматриваться в качестве конечных точек. В качестве не имеющего ограничительного характера примера, конечная точка 324 может представлять собой парковочное место на улице, на автостоянке, на многоуровневой парковке, на внешней парковке у здания, в частном доме, на заброшенной территории, в поле, в гараже здания и т.п.

[88] На фиг. 4 представлена схема процедуры 400 кластеризации, соответствующей не имеющим ограничительного характера вариантам осуществления настоящей технологии.

[89] На фиг. 4 представлены следующие объекты процедуры 400 кластеризации: набор 320 конечных точек, граф 402 дорог, алгоритм 440 кластеризации и набор 480 кластеров.

[90] Граф дорог

[91] Перед получением набора 310 прошлых маршрутов, во время или после него сервер 230 с учетом пункта 312 назначения получает из базы 235 данных граф 402 дорог, соответствующий фрагменту 300 карты.

[92] Следует отметить, что в других вариантах осуществления настоящей технологии граф 402 дорог может соответствовать зоне, окружающей пункт 312 назначения (например, зоне площадью 10 км² вокруг пункта 312 назначения), или может соответствовать всей карте города или региона.

[93] В общем случае граф 402 дорог представляет собой графическое представление фрагмента 300 карты, где все пути, по которым механические транспортные средства (и/или пешеходы) могут следовать в пункт 312 назначения, представлены в виде ребер и вершин.

[94] В представленном здесь варианте осуществления изобретения граф 402 дорог включает в себя набор 405 объектов карты, при этом каждый объект 410 карты представляет собой вершину на графе 402 дорог, имеет класс 414 объекта и по меньшей мере одно местоположение 412 объекта.

[95] Класс 414 объекта такого объекта 410 карты указывает на вид структуры объекта 410 карты на фрагменте 300 карты и/или на признаки объекта 410 карты. В общем случае вид структуры соответствует структуре на участке 300 карты, предназначенной для приема механического транспортного средства.

[96] В некоторых вариантах осуществления настоящей технологии объект карты может иметь один или несколько классов объекта. Дополнительно или в качестве альтернативы, объект 410 карты также может иметь один или несколько подклассов для каждого класса 414 объекта.

[97] В качестве не имеющего ограничительного характера примера класс 414 объекта этого объекта карты может представлять собой класс «участок дороги». Класс «участок дороги» объекта карты указывает на то, что этот объект карты представляет собой участок дороги на фрагменте 300 карты. Таким образом, один ли несколько объектов карты, имеющих класс «участок дороги», могут образовывать дорогу.

[98] Предполагается, что в некоторых вариантах осуществления настоящей технологии объект 410 карты, имеющий класс «участок дороги», также может иметь класс или подкласс, указывающий на вид дороги для этого участка дороги, такой как скоростная автострада или дорога с разделительной полосой, автомагистраль, дорога районного значения или местная дорога. Дополнительно или в качестве альтернативы, объект карты, имеющий класс «участок дороги», также может иметь класс или подкласс, указывающий на то, чему соответствует класс «участок дороги» - дороге, улице, проспекту, бульвару, полосе движения, проезду, улице с газоном, площади или двору.

[99] В других вариантах осуществления настоящей технологии объект 410 карты, имеющий класс «участок дороги», также может иметь один или несколько дополнительных классов или подклассов, которые могут быть основаны на эффективности движения, точках въезда и выезда, предельной скорости движения, расписании занятости, интенсивности движения, цене и т.п.

[100] В качестве не имеющего ограничительного характера примера, класс 414 объекта соответствующего объекта карты может представлять собой класс «препятствие». Класс «препятствие» указывает на препятствие на дороге, которое может быть временным или постоянным и может препятствовать движению механических транспортных средств по этой дороге. Объект карты, имеющий класс «препятствие», может иметь один или несколько других классов или подклассов, указывающих на то, чему соответствует это препятствие - строительной площадке, наличию обломков, тупику, барьеру безопасности, знаку «въезд запрещен», частной дороге или дороге с запрещенным движением и т.п.

[101] В качестве не имеющего ограничительного характера примера, класс 414 объекта соответствующего объекта карты может представлять собой класс «официальная парковка». Класс «официальная парковка» в общем случае может соответствовать муниципальной парковке или частной парковке, связанной с ценой, известной серверному приложению 282 карты. Класс парковки может иметь один или несколько дополнительных классов или подклассов, которые могут указывать на площадку для стоянки, муниципальную или частную парковку, на связанную с парковкой цену, на размещение парковочных мест (параллельное, перпендикулярное, под углом или другое), на размер парковки и т.п.

[102] Объект 410 карты имеет по меньшей мере одно местоположение 412 объекта, которое, например, указывает на начальное местоположение объекта 410 карты и/или на конечную точку объекта 410 карты и/или на промежуточные местоположения между начальной точкой и конечной точкой объекта 410 карты.

[103] Таким образом, можно сказать, что граф 402 дорог позволяет представлять дорожную сеть, окружающую пункт 312 назначения, с использованием набора 405 объектов карты, в котором каждый объект 410 карты связан с одним или несколькими классами объекта.

[104] Очевидно, что на характер класса 414 объекта каждого объекта карты не накладывается каких-либо ограничений. Например, он может быть определен разработчиками на основе данных о прошлых действиях пользователей и официальных данных от города, региона или страны. Описанные выше классы могут быть изменены в зависимости от континента, страны, региона, города или района.

[105] Серверное приложение 282 карты сопоставляет набор 320 конечных точек с графом 402 дорог.

[106] В общем случае серверное приложение 282 карты сопоставляет каждую конечную точку 324 из набора 320 конечных точек с объектом 410 карты и его классом 414 объекта на графе 402 дорог с учетом по меньшей мере одного местоположения 412 объекта, связанного с объектом 410 карты. Серверное приложение 282 карты может сопоставить конечную точку 324 с объектом 410 карты и с классом 414 объекта, если расстояние между конечной точкой 324 и по меньшей мере одним местоположением 412 объекта меньше заранее заданного порогового значения расстояния. В некоторых вариантах осуществления настоящей технологии по меньшей мере одна конечная точка (не показана) из набора 320 конечных точек может быть не связанной с объектом 410 карты графа 402 дорог, например, если расстояние до местоположения 412 объекта превышает заранее заданное пороговое значение расстояния и/или если объект 410 карты отсутствует.

[107] Таким образом, набор 320 конечных точек представлен в виде дополнительных вершин на графе 402 дорог, где каждая конечная точка 324 из по меньшей мере части набора 320 конечных точек связана с объектом 410 карты, а также связана с классом 414 объекта с учетом ее связи с объектом 410 карты.

[108] Серверное приложение 282 карты способно выполнять кластеризацию набора 320 конечных точек, связанных с графом 402 дорог, с использованием алгоритма 440 кластеризации.

[109] Кластеризация

[110] Серверное приложение 282 карты выполняет алгоритм 440 кластеризации. В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии алгоритм 440 кластеризации может быть основан на алгоритме Крускала. Тем не менее, предполагается, что в других не имеющих ограничительного характера вариантах осуществления настоящей технологии могут использоваться другие подходящие алгоритмы.

[111] Вкратце, алгоритм Крускала представляет собой алгоритм MST, который ищет ребро с наименьшим возможным весом, соединяющее любые два дерева в лесу. Дерево MST представляет собой подмножество ребер связного неориентированного графа со взвешенными ребрами, которое соединяет все вершины без циклов и с минимально возможным общим весом ребер. Алгоритм Крускала представляет собой поглощающий алгоритм, который ищет дерево MST для связного взвешенного графа, добавляя на каждом шаге увеличивающие стоимость дуги. Иными словами, для связного неориентированного графа покрывающее дерево графа - это подграф, представляющий собой дерево и соединяющий все вершины, а дерево MST для взвешенного связного неориентированного графа представляет собой покрывающее дерево с весом, не превышающим вес любого другого покрывающего дерева.

[112] Алгоритм Крускала обычно используется при разработке сетей в качестве алгоритма аппроксимации для NP-трудных задач, таких как задача коммивояжера (TSP, Travelling Salesman Problem) и дерево Штейнера (Steiner Tree), а также в других случаях неявного применения. В контексте настоящей технологии алгоритм Крускала модифицирован для выполнения кластеризации набора 320 конечных точек путем реализации функции оценки при выполнении алгоритма MST, обеспечивающего иерархическую кластеризацию набора 320 конечных точек. Функция оценки может представлять собой эвристическую функцию.

[113] В некоторых вариантах осуществления настоящей технологии функция оценки может быть использована алгоритмом 440 кластеризации на каждой итерации и может применять штраф для некоторых признаков (таких как расстояние или класс объекта) путем увеличения взвешенного расстояния между парой конечных точек, имеющих одинаковые признаки.

[114] Функция оценки также может учитывать размер зоны, охватываемой кластером, размер кластера (т.е. количество конечных точек в кластере), классы соседних объектов, не связанных с конечными точками, и т.п.Функция оценки учитывает уровни иерархии классов и/или подклассов объекта.

[115] Взвешенное расстояние между парой конечных точек основано на расстояниях между конечными точками 324 и пунктом 312 назначения, на расстоянии между конечными точками в паре и на классах 414 объектов, связанных с каждой конечной точкой 324.

[116] Таким образом, можно сказать, что набор 320 конечных точек может быть разделен на несколько кластеров так, чтобы минимальный вес связей между элементами в разных кластерах был максимальным. Кластеризация выполняется в иерархическом порядке: сначала каждая конечная точка 324 из набора 320 конечных точек рассматривается в качестве отдельного кластера и алгоритм 440 кластеризации начинается с применения функции оценки и соединения двух конечных точек, имеющих минимальное взвешенное расстояние, затем это действие выполняется со следующей конечной точкой, имеющей минимальное расстояние, и т.д. Кластеризация прекращается, когда остается лишь один кластер, и из всех промежуточных вариантов выбирается вариант с оптимальной функцией оценки (например, минимальной или максимальной).

[117] Предполагается, что в некоторых вариантах осуществления настоящей технологии количество кластеров может быть задано заранее и кластеризация может прекращаться по достижении этого заранее заданного количества кластеров.

[118] Алгоритм кластеризации 440 получает набор 480 кластеров. Каждый кластер 484 имеет размер 486 и центроид 488, а также содержит подмножество набора 320 конечных точек. Каждый кластер 484 из по меньшей мере части набора 480 кластеров может быть связан с объектом 410 карты и с местоположением 412 объекта. Оставшиеся кластеры из набора 480 кластеров могут быть не связаны с объектом 410 карты, а связаны с зоной фрагмента 300 карты или с конечной точкой из набора 320 конечных точек.

[119] Центроид 488 может соответствовать среднему значению расстояний до конечных точек в составе кластера 484 и может быть использован для рекомендации кластера 484 пользователю с учетом направления прибытия пользователя. Иными словами, местоположение центроида 488 может быть использовано в качестве визуального заменителя для представления кластера 484. Например, в некоторых вариантах осуществления настоящей технологии центроид 488 может быть использован для предложения кластера 484 в качестве рекомендации по парковке на основе расстояния между центроидом 488 и промежуточными пунктами маршрута пользователя (не показаны). Размер 486 также может быть использован для рекомендации мест парковки, поскольку чем больше размер зоны парковки, тем выше вероятность наличия свободных мест для парковки.

[120] На фиг. 5 представлен фрагмент 300 карты с набором 480 кластеров в качестве рекомендаций по парковке, полученных путем выполнения алгоритма кластеризации для пункта 312 назначения в соответствии с не имеющими ограничительного характера вариантами осуществления настоящей технологии.

[121] В качестве не имеющего ограничительного характера примера, две группы конечных точек (которые в качестве не имеющего ограничительного характера примера могут представлять собой ансамбль объектов карты, имеющих общие классы «участок дороги», «дорога», «двухсторонний» и «трафик»), могут располагаться вблизи друг друга, но разделяться дорогой с двухсторонним движением. Некоторые известные способы могут объединять эти две группы конечных точек в один кластер вследствие близкого расстояния между ними, но в настоящем варианте осуществления изобретения эти две группы не объединяются в один кластер, поскольку для них будет применен штраф из-за разделяющей их дороги с двухсторонним движением, которая может препятствовать удобному доступу к месту парковки с одной стороны дороги на другую.

[122] Один из множества пользователей, такой как первый пользователь 206, находящийся в пункте отправления в первом транспортном средстве 208, может выбрать или ввести пункт 312 назначения в приложении 280 карты на первом электронном устройстве 204, что инициирует отправку приложением 280 карты серверу 230 запроса 236 карты, включающего в себя запрос маршрута из этого пункта отправления в пункт 312 назначения. Серверное приложение 282 карты может сформировать текущий маршрут из этого пункта отправления в пункт 312 назначения.

[123] В других вариантах осуществления настоящей технологии первый пользователь 206 может лишь интересоваться пунктом 312 назначения и окружающими зонами и может увеличить фрагмент карты, содержащий пункт 312 назначения, или выбрать элемент интерфейса для отображения рекомендаций по парковке, что может инициировать отправку первым электронным устройством 204 запроса рекомендаций по парковке в зонах, окружающих пункт 312 назначения.

[124] Серверное приложение 282 карты извлекает из базы 235 данных связанный с пунктом 312 назначения набор 480 кластеров, по меньшей мере один из которых может быть предоставлен в качестве рекомендации по парковке для пункта 312 назначения. В тех вариантах осуществления изобретения, где первый пользователь 206 запросил текущий маршрут в пункт 312 назначения, серверное приложение 282 карты может на основе текущего маршрута предложить по меньшей мере один кластер из набора 480 кластеров, связанных с пунктом 312 назначения, в качестве рекомендаций по парковке. В некоторых вариантах осуществления настоящей технологии по меньшей мере один кластер из набора 480 кластеров может быть выбран первым и текущий маршрут в пункт 312 назначения может быть предложен на основе выбранного по меньшей мере одного кластера. В других вариантах осуществления изобретения по меньшей мере один кластер из набора 480 кластеров может быть рекомендован на основе текущего местоположения первого пользователя 206. Кроме того, предполагается, что по меньшей мере один кластер может быть рекомендован на основе явных предпочтений пользователя (т.е. указанных первым пользователем 206 в приложении 280 карты) или неявных предпочтений пользователя (т.е. на основе данных о прошлых действиях пользователя), таких как бесплатная парковка, увеличенное парковочное место, парковка не на улице и т.п. В других вариантах осуществления изобретения первому пользователю 206 может быть рекомендован весь набор 480 кластеров. Серверное приложение 282 карты отправляет текущий маршрут, включающий в себя по меньшей мере один кластер из набора 480 кластеров в качестве рекомендаций по парковке. Предполагается, что если первый пользователь 206 изменяет свой маршрут в пункт 312 назначения, то серверное приложение 282 карты может получить соответствующе указание от приложения 280 карты и сформировать второй текущий маршрут и/или предоставить другой кластер из набора 480 кластеров в качестве рекомендаций по парковке.

[125] Описание способа

[126] На фиг. 6 представлена блок-схема способа 600 определения рекомендаций по парковке для пункта назначения, выполняемого сервером 230 согласно вариантам осуществления настоящей технологии, не имеющим ограничительного характера.

[127] Способ 600 может начинаться с шага 602.

[128] Шаг 602: получение с учетом пункта назначения набора прошлых маршрутов, каждый из которых заканчивается в этом пункте назначения, выбранных на карте пользователями, связанными с электронными устройствами.

[129] На шаге 602 серверное приложение 282 карты на сервере 230 с учетом пункта 312 назначения получает из базы 235 данных набор 310 прошлых маршрутов, выбранных на фрагменте 300 карты множеством пользователей (т.е. первым пользователем 206, вторым пользователем 212 и третьим пользователем 218), связанных с электронными устройствами (такими как первое электронное устройство 204, второе электронное устройство 210 и третье электронное устройство 216), при этом каждый прошлый маршрут из набора 310 прошлых маршрутов завершается в пункте 312 назначения.

[130] Затем способ 600 продолжается на шаге 604.

[131] Шаг 604: определение набора конечных точек, связанных с набором прошлых маршрутов, каждая из которых представляет собой фактическую конечную точку по меньшей мере одного пользователя электронного устройства, выбравшего прошлый маршрут в этот пункт назначения на карте, при этом каждая конечная точка представляет собой возможную рекомендацию по парковке.

[132] На шаге 604 серверное приложение 282 карты на сервере 230 определяет набор 320 конечных точек, связанных с набором прошлых маршрутов, каждая из которых представляет собой фактическую конечную точку по меньшей мере одного пользователя электронного устройства, выбравшего прошлый маршрут 314 в пункт 312 назначения на фрагменте 300 карты, при этом каждая конечная точка 324 представляет собой возможную рекомендацию по парковке.

[133] Затем способ 600 продолжается на шаге 606.

[134] Шаг 606: получение из базы данных графа дорог карты, включающего в себя набор объектов карты, каждый из которых характеризуется местоположением объекта на графе дорог и классом объекта, указывающим на структуру на карте.

[135] На шаге 608 серверное приложение 282 карты на сервере 230 получает из базы 235 данных для фрагмента 300 карты граф 402 дорог, содержащий набор 405 объектов карты, каждый из которых имеет соответствующее местоположение 412 объекта и класс 414 объекта, указывающий на структуру на фрагменте 300 карты. В некоторых вариантах осуществления настоящей технологии класс 414 объекта может представлять собой «участок дороги», или «препятствие», или «известное парковочное место». В некоторых вариантах осуществления настоящей технологии класс «участок дороги» включает в себя скоростную автостраду, автомагистраль, дорогу районного значения или местную дорогу.

[136] Затем способ 600 продолжается на шаге 608.

[137] Шаг 608: сопоставление каждой конечной точки из по меньшей мере части набора конечных точек с по меньшей мере одним объектом карты графа дорог с учетом расстояния между этой конечной точкой и по меньшей мере одним местоположением объекта, связанным с каждым из этих объектов карты.

[138] На шаге 608 серверное приложение 282 карты на сервере 230 сопоставляет каждую конечную точку 324 из по меньшей мере части набора 320 конечных точек с по меньшей мере одним объектом 410 карты графа 402 дорог, если расстояние между конечной точкой 324 и по меньшей мере одним местоположением 412 объекта, связанным с каждым объектом 410 карты, меньше заранее заданного расстояния.

[139] В некоторых вариантах осуществления настоящей технологии по меньшей мере одна конечная точка (не показана) из набора 320 конечных точек может быть не связанной с объектом 410 карты графа 402 дорог, например, если отсутствует объект 410 карты, расстояние до которого меньше заранее заданного расстояния, или при недостаточности данных.

[140] Затем способ 600 продолжается на шаге 610.

[141] Шаг 610: кластеризация набора конечных точек с целью получения набора кластеров на графе дорог, каждый из которых содержит подмножество конечных точек, при этом каждый кластер из по меньшей мере части набора кластеров связан с по меньшей мере одним объектом карты и с местоположением этого объекта, а кластеризация выполняется на основе пункта назначения, конечных точек и классов объектов карты.

[142] На шаге 610 серверное приложение 282 карты на сервере 230 выполняет алгоритм 440 кластеризации с целью кластеризации набора 320 конечных точек и получения набора 480 кластеров, при этом каждый кластер 484 содержит подмножество набора 320 конечных точек.

[143] Кластеризация выполняется с учетом пункта 312 назначения, конечных точек 324, класса 414 объекта и местоположения 412 объекта соответствующих объектов 410 карты.

[144] В некоторых вариантах осуществления настоящей технологии каждый кластер 484 из по меньшей мере части набора 480 кластеров может быть связан с объектом 410 карты и с его классом 414 объекта, а по меньшей мере один оставшийся кластер (не показан) из набора 480 кластеров не обязательно должен быть связан с объектом из набора 405 объектов карты, например, при недостаточности данных о фрагменте 300 карты, и может быть привязан к области фрагмента 300 карты или к некоторой точке из набора 320 конечных точек.

[145] В некоторых вариантах осуществления настоящей технологии количество кластеров в наборе 480 кластеров может быть задано заранее. В некоторых вариантах осуществления настоящей технологии алгоритм 440 кластеризации может быть основан на модифицированном варианте алгоритма Крускала и использовать функцию оценки на каждом итеративном шаге. В некоторых вариантах осуществления настоящей технологии алгоритм 440 кластеризации может использовать функцию эвристической оценки. Алгоритм 440 кластеризации может выполнять кластеризацию в иерархическом порядке, когда сначала каждая конечная точка 324 рассматривается как кластер. Каждый кластер 484 характеризуется размером 486 и центроидом 488, которые могут быть использованы для определения по меньшей мере одного кластера 484 в качестве рекомендаций по парковке для пункта 312 назначения.

[146] На этом способ 600 завершается.

[147] Затем способ 600 может быть повторен для набора пунктов назначения (не показан) с целью получения набора кластеров (не показан) для предоставления в качестве рекомендаций по парковке для каждого пункта назначения из набора пунктов назначения. На способ выбора пунктов назначения из набора пунктов назначения не накладывается каких-либо ограничений. Например, этот выбор может быть основан на популярности пункта назначения.

[148] Серверное приложение 282 карты на сервере 230 может сохранять в базе 235 данных для каждого пункта назначения каждый набор кластеров, по меньшей мере один кластер из которого может использоваться в качестве рекомендации по парковке для этого пункта назначения из набора пунктов 312 назначения.

[149] По меньшей мере один кластер из набора кластеров может быть предоставлен серверным приложением 282 карты приложению 280 карты в качестве рекомендации по парковке для соответствующего пункта назначения. В не имеющем ограничительного характера примере увеличение пользователем фрагмента карты, содержащего пункт назначения, и заблаговременная активация опции для отображения рекомендаций по парковке либо выбор пользователем элемента интерфейса для отображения рекомендаций по парковке для этого пункта назначения может инициировать отправку приложением 280 карты запроса 236 карты серверному приложению 282 карты. Серверное приложение 282 карты может извлечь по меньшей мере один кластер из набора кластеров из базы 235 данных и инициировать отображение в приложении 280 карты по меньшей мере одного кластера в качестве рекомендаций по парковке для этого пункта назначения. По меньшей мере один кластер из набора кластеров также может быть предоставлен в качестве рекомендаций по парковке пользователю, запросившему маршрут в этот пункт назначения.

[150] На фиг. 7 представлен способ 700 предоставления рекомендаций по парковке для пункта назначения пользователю электронного устройства, такому как первый пользователь 206, связанный с первым электронным устройством 204.

[151] Способ 700 выполняется серверным приложением 282 карты на сервере 230 после выполнения способа 600.

[152] Способ 700 начинается с шага 702.

[153] Шаг 702: получение запроса текущего маршрута в пункт назначения, включающего в себя указание на пункт отправления.

[154] На шаге 702 серверное приложение 282 карты на сервере 230 получает от первого электронного устройства 204 запрос 236 карты, касающийся текущего маршрута в пункт 312 назначения и содержащий указание на пункт 308 отправления.

[155] Способ 700 продолжается на шаге 704.

[156] Шаг 704: определение текущего маршрута на карте из пункта отправления в пункт назначения и по меньшей мере одного кластера, содержащего подмножество конечных точек, в качестве рекомендации по парковке для этого пункта назначения.

[157] На шаге 704 серверное приложение 282 карты на сервере 230 определяет текущий маршрут на фрагменте 300 карты из пункта 308 отправления в пункт 312 назначения и по меньшей мере один кластер 484, содержащий подмножество набора 320 конечных точек, в качестве рекомендации по парковке для пункта 312 назначения. На способ определения текущего маршрута из пункта отправления в пункт 312 назначения не накладывается каких-либо ограничений. Этот маршрут может быть сформирован с учетом расстояния, трафика, времени суток и других факторов с целью сокращения до минимума времени пребывания в пути пользователя на его транспортном средстве. В некоторых вариантах осуществления настоящей технологии серверное приложение 282 карты сначала может выбрать по меньшей мере один кластер 484, содержащий подмножество набора 320 конечных точек, в качестве рекомендации по парковке для пункта 312 назначения (например, на основе доступности парковки в аналогичный период времени в прошлом), а затем сформировать текущий маршрут на основе по меньшей мере одного кластера 484.

[158] Способ 700 продолжается на шаге 706.

[159] Шаг 706: отправка электронному устройству текущего маршрута, включающего в себя рекомендацию по парковке.

[160] На шаге 706 серверное приложение 282 карты на сервере 230 отправляет приложению 280 карты третьего электронного устройства 216 текущий маршрут в пункт 312 назначения, включающий в себя по меньшей мере один кластер 484, содержащий подмножество набора 320 конечных точек, в качестве рекомендаций по парковке.

[161] На этом способ 700 завершается.

[162] Специалистам в данной области техники должно быть очевидно, что по меньшей некоторые варианты осуществления настоящей технологии преследуют цель расширения арсенала технических решений определенной технической проблемы, а именно, усовершенствование определения рекомендаций по парковке для пункта назначения на основе прошлых пользовательских данных с использованием алгоритма MST в качестве алгоритма иерархической кластеризации, что уменьшает время, требуемое для формирования сервером набора кластеров в качестве рекомендаций по парковке, и может обеспечить более адекватные рекомендации пользователям клиентских устройств. Такие технические решения могут обеспечить экономию ресурсов, например, объема памяти, производительности и времени в клиентских устройствах и на сервере.

[163] Очевидно, что не все упомянутые в данном описании технические эффекты должны присутствовать в каждом варианте осуществления настоящей технологии. Например, возможны варианты осуществления настоящей технологии, когда пользователь не получает некоторые из этих технических эффектов, или другие варианты реализации, когда пользователь получает другие технические эффекты либо технический эффект отсутствует.

[164] Некоторые из этих шагов и передаваемых или принимаемых сигналов хорошо известны в данной области техники и по этой причине опущены в некоторых частях описания для упрощения. Сигналы могут передаваться или приниматься с использованием оптических средств (таких как волоконно-оптическое соединение), электронных средств (таких как проводное или беспроводное соединение) и механических средств (например, основанных на давлении, температуре или любом другом подходящем физическом параметре).

[165] Для специалиста в данной области могут быть очевидными изменения и усовершенствования описанных выше вариантов осуществления настоящей технологии. Предшествующее описание приведено исключительно в иллюстративных целях, а не для ограничения объема изобретения. Объем охраны настоящей технологии определяется исключительно объемом приложенной формулы изобретения.

1. Компьютерный способ определения рекомендаций по парковке для пункта назначения на карте, отображаемой на электронном устройстве, который выполняется сервером, связанным с электронным устройством и с базой данных и выполняющим алгоритм кластеризации, и включает в себя:

- получение из базы данных с учетом пункта назначения набора прошлых маршрутов, каждый из которых заканчивается в этом пункте назначения, выбранных на карте пользователями, связанными с электронными устройствами;

- определение сервером набора конечных точек, связанных с набором прошлых маршрутов, каждая из которых представляет собой фактическую конечную точку по меньшей мере одного пользователя электронного устройства, выбравшего прошлый маршрут в этот пункт назначения на карте, и представляет собой возможную рекомендацию по парковке;

- получение из базы данных графа дорог карты, включающего в себя набор объектов карты, каждый из которых характеризуется местоположением объекта и классом объекта, указывающим на вид структуры данного объекта на карте;

- кластеризацию сервером набора конечных точек с целью получения набора кластеров, каждый из которых содержит подмножество конечных точек, при этом каждый кластер из по меньшей мере части набора кластеров связан с по меньшей мере одним объектом карты и с местоположением этого объекта, а кластеризация выполняется на основе:

- пункта назначения,

- конечных точек,

- местоположений объекта и

- классов объектов карты;

- получение от электронного устройства запроса текущего маршрута в пункт назначения, включающего в себя указание на пункт отправления;

- определение сервером текущего маршрута на карте из пункта отправления в пункт назначения и по меньшей мере одного кластера, содержащего подмножество конечных точек, в качестве рекомендации по парковке для этого пункта назначения; и

- отправку электронному устройству текущего маршрута, включающего в себя рекомендацию по парковке.

2. Способ по п. 1, отличающийся тем, что набор конечных точек определяется так, что расстояние между каждой конечной точкой и пунктом назначения меньше заранее заданного порогового значения.

3. Способ по п. 2, отличающийся тем, что класс объекта указывает на иерархический уровень объекта карты на графе дорог, а кластеризация выполняется в иерархическом порядке.

4. Способ по п. 3, отличающийся тем, что каждый кластер характеризуется центроидом и размером, а определение по меньшей мере одного кластера, содержащего подмножество конечных точек, в качестве рекомендации по парковке, основано на центроиде и размере по меньшей мере одного кластера.

5. Способ по п. 4, отличающийся тем, что кластеризация выполняется с использованием функции эвристической оценки.

6. Способ по п. 5, отличающийся тем, что алгоритм кластеризации основан на алгоритме Крускала.

7. Способ по п. 6, отличающийся тем, что набор кластеров содержит заранее заданное количество кластеров.

8. Способ по п. 2, отличающийся тем, что каждый прошлый маршрут связан с периодом времени, проведенного по меньшей мере одним пользователем электронного устройства в конечной точке, а определение набора конечных точек дополнительно зависит от превышения этим периодом времени заранее заданного порогового значения времени.

9. Способ по п. 6, отличающийся тем, что до кластеризации он дополнительно включает в себя сопоставление сервером каждой конечной точки из по меньшей мере части набора конечных точек с по меньшей мере одним объектом карты с учетом расстояния между конечной точкой и по меньшей мере одним местоположением объекта, связанным с каждым из этих объектов карты.

10. Способ по п. 7, отличающийся тем, что класс объекта представляет собой «участок дороги», или «препятствие», или «известное парковочное место».

11. Способ по п. 10, отличающийся тем, что класс «участок дороги» включает в себя скоростную автостраду, автомагистраль, дорогу районного значения или местную дорогу.

12. Сервер для определения рекомендаций по парковке для пункта назначения на карте, отображаемой на электронном устройстве, связанном с сервером, который связан с базой данных и содержит процессор и машиночитаемый физический носитель информации, содержащий команды, при этом процессор выполнен с возможностью выполнения следующих действий при исполнении команд:

- получение из базы данных с учетом пункта назначения набора прошлых маршрутов, каждый из которых заканчивается в пункте назначения, выбранных на карте пользователями, связанными с электронными устройствами;

- определение набора конечных точек, связанных с набором прошлых маршрутов, каждая из которых представляет собой фактическую конечную точку по меньшей мере одного пользователя электронного устройства, выбравшего прошлый маршрут в пункт назначения на карте, и представляет собой возможную рекомендацию по парковке;

- получение из базы данных графа дорог карты, включающего в себя набор объектов карты, каждый из которых характеризуется местоположением объекта и классом объекта, указывающим на вид структуры данного объекта на карте;

- кластеризация набора конечных точек с целью получения набора кластеров, каждый из которых содержит подмножество конечных точек, при этом каждый кластер из по меньшей мере части набора кластеров связан с по меньшей мере одним объектом карты и с местоположением этого объекта, а кластеризация выполняется на основе:

- пункта назначения,

- конечных точек,

- местоположений объекта и

- классов объектов карты;

- получение от электронного устройства запроса текущего маршрута в пункт назначения, включающего в себя указание на пункт отправления;

- определение текущего маршрута на карте из пункта отправления в пункт назначения и по меньшей мере одного кластера, содержащего подмножество конечных точек, в качестве рекомендации по парковке для пункта назначения;

- отправка электронному устройству текущего маршрута, включающего в себя рекомендацию по парковке.

13. Сервер по п. 12, отличающийся тем, что набор конечных точек определяется так, что расстояние между каждой конечной точкой и пунктом назначения меньше заранее заданного порогового значения.

14. Сервер по п. 13, отличающийся тем, что класс объекта указывает на иерархический уровень объекта карты на графе дорог, а кластеризация выполняется в иерархическом порядке.

15. Сервер по п. 14, отличающийся тем, что каждый кластер характеризуется центроидом и размером, а определение по меньшей мере одного кластера, содержащего подмножество конечных точек, в качестве рекомендации по парковке, основано на центроиде и размере по меньшей мере одного кластера.

16. Сервер по п. 15, отличающийся тем, что кластеризация выполняется с использованием функции эвристической оценки.

17. Сервер по п. 16, отличающийся тем, что алгоритм кластеризации основан на алгоритме Крускала.

18. Сервер по п. 17, отличающийся тем, что набор кластеров содержит заранее заданное количество кластеров.

19. Сервер по п. 13, отличающийся тем, что каждый прошлый маршрут связан с периодом времени, проведенного по меньшей мере одним пользователем электронного устройства в конечной точке, а определение набора конечных точек дополнительно зависит от превышения этим периодом времени заранее заданного порогового значения времени.

20. Сервер по п. 17, отличающийся тем, что процессор дополнительно выполнен с возможностью выполнения до кластеризации сопоставления каждой конечной точки из по меньшей мере части набора конечных точек с по меньшей мере одним объектом карты с учетом расстояния между конечной точкой и по меньшей мере одним местоположением объекта, связанным с каждым из этих объектов карты.

21. Сервер по п. 18, отличающийся тем, что класс объекта представляет собой «участок дороги», или «препятствие», или «известное парковочное место».

22. Сервер по п. 19, отличающийся тем, что класс «участок дороги» включает в себя скоростную автостраду, автомагистраль, дорогу районного значения или местную дорогу.